Lowest Common Ancestor of a Binary Tree in Rust

Question

I am trying to solve the lowest common ancestor problem in Rust. It is guaranteed that the id's of the tree are unique. It is also guaranteed that the two nodes which we are looking for in the tree actually exist. My code is below.

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


// Definition for a binary tree node.
#[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
    }
  }
}

// result enum
#[derive(Debug, PartialEq, Eq)]
pub enum LcaRes {
    NotFound,
    FoundP,
    FoundQ,
    FoundBoth(Rc<RefCell<TreeNode>>),
}

struct Solution;

impl Solution {
    pub fn find(root: Rc<RefCell<TreeNode>>, p: Rc<RefCell<TreeNode>>) -> bool{
        if root.borrow().val == p.borrow().val {
            return true;
        }
        match (&root.borrow().left, &root.borrow().right) {
            (None, None) => false,
            (Some(l), None) => Solution::find(l.clone(), p),
            (None, Some(r)) => Solution::find(r.clone(), p),
            (Some(l), Some(r)) => Solution::find(l.clone(), p.clone()) || Solution::find(r.clone(), p),
        }
    }
    pub fn lca_aux(root: Rc<RefCell<TreeNode>>, p: Rc<RefCell<TreeNode>>, q: Rc<RefCell<TreeNode>>) -> LcaRes{
        if root.borrow().val == p.borrow().val {
            if Solution::find(root.clone(), q.clone()) { 
                return LcaRes::FoundBoth(root.clone()); 
            }
            else { return LcaRes::FoundP; }
        }
        if root.borrow().val == q.borrow().val {
            if Solution::find(root.clone(), p.clone()) {
                return LcaRes::FoundBoth(root.clone()); 
            }
            else { return LcaRes::FoundQ; }
        }
        match (&root.borrow().left, &root.borrow().right) {
            (None, None) => LcaRes::NotFound,
            (Some(l), None) => Solution::lca_aux(l.clone(), p, q),
            (None, Some(r)) => Solution::lca_aux(r.clone(), p, q),
            (Some(l), Some(r)) => {
                let result_l = Solution::lca_aux(l.clone(), p.clone(), q.clone());
                match result_l {
                    LcaRes::FoundBoth(_) => result_l,
                    LcaRes::NotFound => Solution::lca_aux(r.clone(), p, q),
                    LcaRes::FoundP => {
                        if Solution::find(r.clone(), q.clone()) { 
                            LcaRes::FoundBoth(root.clone())
                        }
                        else { LcaRes::FoundP }
                    },
                    LcaRes::FoundQ => {
                        if Solution::find(r.clone(), p.clone()) {
                            LcaRes::FoundBoth(root.clone())
                        }
                        else { LcaRes::FoundQ }
                    }
                }
            }
        }
    }
    pub fn lowest_common_ancestor(root: Option<Rc<RefCell<TreeNode>>>, p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        match (root, p, q) {
            (Some(root), Some(p), Some(q)) => {
                match Solution::lca_aux(root.clone(), p, q) {
                    LcaRes::FoundBoth(lca) => Some(lca),
                    _ => None,
                }
            }
            _ => None,
        }
    }
    pub fn tree_builder(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        // build a binary tree from a vector of values
        // the vector contains the elements of the tree layer by layer
        // the first element is the root
        // a -1 indicates no node at this position

        if nums.len() == 0 {
            return None;
        }

        let mut queue = VecDeque::new();
        let root = Rc::new(RefCell::new(TreeNode::new(nums[0])));
        queue.push_back(root.clone());
        let mut i = 1;
        while i < nums.len() {
            let node = queue.pop_front().unwrap();
            if nums[i] != -1 {
                node.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
                queue.push_back(node.borrow_mut().left.as_ref().unwrap().clone());
            }
            i += 1;
            if i < nums.len() {
                if nums[i] != -1 {
                    node.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
                    queue.push_back(node.borrow_mut().right.as_ref().unwrap().clone());
                }
                i += 1;
            }
        }
        queue.pop_front();

        Some(root)
    }

    pub fn tree_stringify(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        // stringify a binary tree using parantheses, recursively
        // (root (left) (right))

        match root {
            None => "()".to_string(),
            Some(root) => {
                format!("({} {} {})", 
                    root.borrow().val, 
                    Solution::tree_stringify(root.borrow().left.clone()),
                    Solution::tree_stringify(root.borrow().right.clone()))
            }
        }
    }
        
}



fn main(){
    let nums = vec![3,5,1,6,2,0,8,-1,-1,7,4];
    let root = Solution::tree_builder(nums);
    println!("{}", Solution::tree_stringify(root.clone()));
    let p = Rc::new(RefCell::new(TreeNode::new(5)));
    let q = Rc::new(RefCell::new(TreeNode::new(4)));
    let lca = Solution::lowest_common_ancestor(root, Some(p), Some(q));
    println!("{}", lca.unwrap().borrow().val);
    println!("");


    let nums2 = vec![1, 2, 3, -1, 4];
    let root2 = Solution::tree_builder(nums2);
    println!("{}", Solution::tree_stringify(root2.clone()));
    let p2 = Rc::new(RefCell::new(TreeNode::new(4)));
    let q2 = Rc::new(RefCell::new(TreeNode::new(3)));
    // println!("{:?}", Solution::lca_aux(root2.unwrap().borrow().left.clone().unwrap(), p2.clone(), q2.clone()));
    let lca2 = Solution::lowest_common_ancestor(root2, Some(p2), Some(q2));
    println!("{:?}", lca2.unwrap().borrow().val);
    
}

I am looking for feedback on the following things:

1. Is this the best way to represent a binary tree in Rust? (For the rest of the questions, please assume that it is)
2. Am I wrapping and unwrapping the Option<Rc<RefCell<_>>> values correctly? What is the most idiomatic way to pattern match on these objects?
3. Is using the sum type LcaRes recommended in order to implement lca_aux?
4. Anything else that is meant to make my code as close to idiomatic rust as possible.

Answer 1

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


// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

Rc and RefCell are usually signs that the code isn't very rusty. It would be better to use Option<Box<TreeNode>>. Rc and RefCell move borrow checking to runtime, which is okay sometimes, but ideally in Rust we prefer to have the borrow checker operate at compile time.

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

// result enum
#[derive(Debug, PartialEq, Eq)]
pub enum LcaRes {
    NotFound,
    FoundP,
    FoundQ,
    FoundBoth(Rc<RefCell<TreeNode>>),
}

struct Solution;

You define this empty Solution struct and then methods on it. That's kinda odd. You seem to be trying to define a namespace? You can do that more intuitively by using mod solution { ... } .

impl Solution {
    pub fn find(root: Rc<RefCell<TreeNode>>, p: Rc<RefCell<TreeNode>>) -> bool{

Even if you use Rc<RefCell<...>> you probably should just take &TreeNode here. You can get rid of a lot of borrow() and clone() calls. That should help performance and just be simpler.

        if root.borrow().val == p.borrow().val {
            return true;
        }
        match (&root.borrow().left, &root.borrow().right) {
            (None, None) => false,
            (Some(l), None) => Solution::find(l.clone(), p),
            (None, Some(r)) => Solution::find(r.clone(), p),
            (Some(l), Some(r)) => Solution::find(l.clone(), p.clone()) || Solution::find(r.clone(), p),
        }
    }

Furthermore, the function is just more complicated then it needs to be:

pub fn find(root: &TreeNode, p: &TreeNode) -> bool {
    root.val == p.val
        || root.left.as_ref().map_or(false, |node| Solution::find(&node.borrow(), p))
        || root.right.as_ref().map_or(false, |node| Solution::find(&node.borrow(), p))
}

...

    pub fn tree_builder(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        // build a binary tree from a vector of values
        // the vector contains the elements of the tree layer by layer
        // the first element is the root
        // a -1 indicates no node at this position

        if nums.len() == 0 {
            return None;
        }

        let mut queue = VecDeque::new();
        let root = Rc::new(RefCell::new(TreeNode::new(nums[0])));
        queue.push_back(root.clone());
        let mut i = 1;
        while i < nums.len() {

A possibly better approach is to use iterators.

let mut nums = nums.into_iter();
while let Some(value) = nums.next() {
    ...
    if let Some(second_value) = nums.next() {
         ...
    }
}

            let node = queue.pop_front().unwrap();
            if nums[i] != -1 {
                node.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
                queue.push_back(node.borrow_mut().left.as_ref().unwrap().clone());
            }
            i += 1;
            if i < nums.len() {
                if nums[i] != -1 {
                    node.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(nums[i]))));
                    queue.push_back(node.borrow_mut().right.as_ref().unwrap().clone());
                }
                i += 1;
            }
        }
        queue.pop_front();

Its kinda pointless to pop a queue you are about to throw away.

        Some(root)
    }

This function does a layer by layer construction. That is the root, then the children of the root, then the grandchildren of the roots. That's a little unusual, things are more typically donen in-order, pre-order, or post-order.

    pub fn tree_stringify(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        // stringify a binary tree using parantheses, recursively
        // (root (left) (right))

        match root {
            None => "()".to_string(),
            Some(root) => {
                format!("({} {} {})", 
                    root.borrow().val, 
                    Solution::tree_stringify(root.borrow().left.clone()),
                    Solution::tree_stringify(root.borrow().right.clone()))
            }
        }
    }

This works, but will have to do an allocation at each level of the tree. You could consider a version that appends into a String as it goes.

}



fn main(){
    let nums = vec![3,5,1,6,2,0,8,-1,-1,7,4];
    let root = Solution::tree_builder(nums);
    println!("{}", Solution::tree_stringify(root.clone()));
    let p = Rc::new(RefCell::new(TreeNode::new(5)));
    let q = Rc::new(RefCell::new(TreeNode::new(4)));

It's rather bizarre to search by creating nodes that violate your claim that the ids are unique. It would make more sense to search by id, passing the id as a parameter.

    let lca = Solution::lowest_common_ancestor(root, Some(p), Some(q));
    println!("{}", lca.unwrap().borrow().val);
    println!("");


    let nums2 = vec![1, 2, 3, -1, 4];
    let root2 = Solution::tree_builder(nums2);
    println!("{}", Solution::tree_stringify(root2.clone()));
    let p2 = Rc::new(RefCell::new(TreeNode::new(4)));
    let q2 = Rc::new(RefCell::new(TreeNode::new(3)));
    // println!("{:?}", Solution::lca_aux(root2.unwrap().borrow().left.clone().unwrap(), p2.clone(), q2.clone()));
    let lca2 = Solution::lowest_common_ancestor(root2, Some(p2), Some(q2));
    println!("{:?}", lca2.unwrap().borrow().val);
    
}