Iterative traversal of Binary Tree & Interior Mutability

help
1

I'm working with a Binary Tree defined as such:
(View in Playground)

type Tree = Rc<RefCell<TreeNode>>;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Tree>,
    pub right: Option<Tree>,
}

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

Id like to create an insert function, and can do so using a stack just fine:

pub fn insert(root: &mut Option<Tree>, val: i32) {
    let mut current_node = match root {
        Some(node) => node.clone(),
        None => {
            *root = Some(Rc::new(RefCell::new(TreeNode::new(val))));
            return;
        }
    };
    //// USING STACK
    let mut stack: Vec<Tree> = Vec::new();
    stack.push(current_node.clone());
    while let Some(node) = stack.pop() {
        let mut node = node.borrow_mut();
        if val < node.val {
            match &node.left {
                None => node.left = Some(Rc::new(RefCell::new(TreeNode::new(val)))),
                Some(n) => stack.push(n.clone()),
            }
        } else {
            match &node.right {
                None => node.right = Some(Rc::new(RefCell::new(TreeNode::new(val)))),
                Some(n) => stack.push(n.clone()),
            }
        }
    }
}

But, shouldn't it be possible to traverse the nodes with a pointer/RC and avoid the stack? My first attempt runs in to the borrow checker. Is there something I'm missing here?

pub fn insert(root: &mut Option<Tree>, val: i32) {
    let mut current_node = match root {
        Some(node) => node.clone(),
        None => {
            *root = Some(Rc::new(RefCell::new(TreeNode::new(val))));
            return;
        }
    };
    ////USING POINTER?
    loop {
        let node_value = current_node.borrow().val;

        if val < node_value {
            if current_node.borrow().left.is_none() {
                current_node.borrow_mut().left = Some(Rc::new(RefCell::new(TreeNode::new(val))));
            } else {
                current_node = current_node.borrow().left.as_ref().unwrap().clone();
            }
        } else {
            if current_node.borrow().right.is_none() {
                current_node.borrow_mut().right = Some(Rc::new(RefCell::new(TreeNode::new(val))));
            } else {
                current_node = current_node.borrow().right.as_ref().unwrap().clone();
            }
        }
    }

The borrow checker error:

error[E0506]: cannot assign to `current_node` because it is borrowed
    --> src/merge_two_bin_trees.rs:54:17
     |
54   |                 current_node = current_node.borrow().right.as_ref().unwrap().clone();
     |                 ^^^^^^^^^^^^   ---------------------                                - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, TreeNode>`
     |                 |              |
     |                 |              borrow of `current_node` occurs here
     |                 |              a temporary with access to the borrow is created here ...
     |                 assignment to borrowed `current_node` occurs here
     |
     = note: borrow occurs due to deref coercion to `RefCell<TreeNode>`

I understand this borrow checker error, but is there a way to accomplish this?

(View in Playground)

2 
-current_node = current_node.borrow().left.as_ref().unwrap().clone();
+let n = current_node.borrow().left.as_ref().unwrap().clone();
+current_node = n;

Rust Playground

Update:

  • the error msg is friendlier when writing current_node = {current_node.borrow().right.clone()}.unwrap();
    that reminds you of dropping the temporary early
error[E0506]: cannot assign to `current_node` because it is borrowed
  --> src/lib.rs:75:17
   |
75 |                 current_node = {current_node.borrow().right.clone()}.unwrap();
   |                 ^^^^^^^^^^^^    ---------------------                        - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, TreeNode>`
   |                 |               |
   |                 |               `current_node` is borrowed here
   |                 |               a temporary with access to the borrow is created here ...
   |                 `current_node` is assigned to here but it was already borrowed
   |
   = note: the temporary is part of an expression at the end of a block;
           consider forcing this temporary to be dropped sooner, before the block's local variables are dropped
   = note: borrow occurs due to deref coercion to `RefCell<TreeNode>`
note: deref defined here
  --> /rustc/84c898d65adf2f39a5a98507f1fe0ce10a2b8dbc/library/alloc/src/rc.rs:1550:5
help: for example, you could save the expression's value in a new local variable `x` and then make `x` be the expression at the end of the block
   |
75 |                 current_node = {let x = current_node.borrow().right.clone(); x}.unwrap();
   |                                 +++++++                                    +++
2 Likes
3

hahah. Awesome. Thank you. End the borrow by cloning to a variable. Duh.

4

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.