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

[ademyanchuk]

Hi

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

[H2CO3]

@ademyanchuk

My main concern is all the clone calls in recursive function are quite expansive.

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)
}

[ademyanchuk]

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