How not to use clone in Binary Search Tree recursive function?

Hi :slight_smile:

Below is my solution for leetcode lowest common ancestor for two nodes in the binary search tree.
Question.

The main pain point is all those Rc and RefCell things. I can make it work, but I think there is a better way to do it. My main concern is all the clone calls in recursive function are quite expansive. Would appreciate, if you point me towards better direction!

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

pub fn lowest_common_ancestor(
    root: Option<Rc<RefCell<TreeNode>>>,
    p: Option<Rc<RefCell<TreeNode>>>,
    q: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    fn lca(node: Option<Rc<RefCell<TreeNode>>>, pv: i32, qv: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if let Some(node) = node {
            let val = node.borrow().val;
            if pv < val && qv < val {
                return lca(node.borrow().left.clone(), pv, qv);
            } else if pv > val && qv > val {
                return lca(node.borrow().right.clone(), pv, qv);
            } else {
                return Some(node);
            }
        }
        None
    }
    let pv = p.unwrap().borrow().val;
    let qv = q.unwrap().borrow().val;
    lca(root, pv, qv)
}

Thank you in advance and all the best,
Alexey

Did you measure it? Cloning an Rc is literally an integer increment, nothing else.


Anyway, it doesn't look like you need Rc or RefCell at all? Just use references:

fn lca(node: Option<&TreeNode>, pv: i32, qv: i32) -> Option<&TreeNode> {
    node.and_then(|node| {
        let val = node.val;
        if pv < val && qv < val {
            lca(node.left.as_deref(), pv, qv)
        } else if pv > val && qv > val {
            lca(node.right.as_deref(), pv, qv)
        } else {
            Some(node)
        }
    })
}

pub fn lowest_common_ancestor<'a>(
    root: &'a TreeNode,
    p: &TreeNode,
    q: &TreeNode,
) -> Option<&'a TreeNode> {
    lca(Some(root), p.val, q.val)
}
2 Likes

Thanks for the quick reply. No, I didn't measure it. Some mental model I guess, if it is clone it should be expansive. I don't have deep knowledge about Rc, but it does make sense about only incrementing an integer (Rc stands for reference count, if I am not wrong). Thanks again :slight_smile:

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.