How to implement insertion into BST iteratively in Rust?

Question

I'm trying to implement an algorithm for insertion into BST (binary search tree) in Rust. I did it recursively, but am having problems implementing the iterative solution. I'm struggling to borrow a child mutably when iterating.

I'm probably approaching it wrong and am looking for cues what's the best idiomatic way of writing such an algorithm.

Notes:

• I'd like to avoid cloning the nodes (unless it's Rc::clone()).
• It's a problem from LeetCode so the signature and types cannot be changed

Code (In Rust playground)

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

pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}


// Returns the (possibly new) root of the tree
fn insert_into_bst_iterative(
    root: Option<Rc<RefCell<TreeNode>>>,
    val: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let mut root = root;
    let mut cur_node = &mut root;

    while let Some(cur_node_rc) = cur_node {
        let mut cur_node_inner = cur_node_rc.borrow_mut();
        if val <= cur_node_inner.val {
            cur_node = &mut cur_node_inner.left;
        } else {
            cur_node = &mut cur_node_inner.right;
        }
    }

    cur_node.replace(Rc::new(RefCell::new(TreeNode {
        val,
        left: None,
        right: None,
    })));

    return root;
}

Error

   Compiling playground v0.0.1 (/playground)
error[E0597]: `cur_node_inner` does not live long enough
  --> src/lib.rs:21:29
   |
18 |     while let Some(cur_node_rc) = cur_node {
   |                                   -------- borrow later used here
19 |         let mut cur_node_inner = cur_node_rc.borrow_mut();
   |             ------------------ binding `cur_node_inner` declared here
20 |         if val <= cur_node_inner.val {
21 |             cur_node = &mut cur_node_inner.left;
   |                             ^^^^^^^^^^^^^^ borrowed value does not live long enough
...
25 |     }
   |     - `cur_node_inner` dropped here while still borrowed

For more information about this error, try `rustc --explain E0597`.
error: could not compile `playground` (lib) due to 1 previous error

Answer 1

You won't be able to take long-lived references to anything returned by RefCell::borrow because the value returned only lives as long as the RefCell, which only lasts for the loop iteration. You'll need to Rc::clone the values as you iterate over them to produce a value that lives long enough to be stored in cur_node. (Also, taking a (mutable) reference to an Option is generally a code smell; you probably want opt.as_ref() or opt.as_mut() to get Option<&T> or Option<&mut T>.)

Also note that once we start using Rc::clone, we have to swap the order of the None-checks because when the loop exits, cur_node will be None and, since you can't taken mutable references into the original tree, replacing the value with a new value will just create it on the stack, then lose it. You have to insert the new value into the parent by flipping the order of the check for None.

// Returns the (possibly new) root of the tree
fn insert_into_bst_iterative(
    root: Option<Rc<RefCell<TreeNode>>>,
    val: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
    let new_val = Some(Rc::new(RefCell::new(TreeNode {
        val,
        left: None,
        right: None,
    })));

    let Some(mut cur_node) = root.clone() else {
        return new_val;
    };

    loop {
        let mut cur_node_inner = cur_node.borrow_mut();

        let new_node = if val <= cur_node_inner.val {
            &mut cur_node_inner.left
        } else {
            &mut cur_node_inner.right
        };

        let Some(new_node) = new_node else {
            *new_node = new_val;
            return root;
        };

        let new_node = Rc::clone(new_node);
        drop(cur_node_inner);

        cur_node = new_node;
    }
}

Also I'd ordinarily say for a binary tree, which has no cycles, you can just use a Box instead of Rc<RefCell>, but if you really can't change the types then this will have to do. (If you could use Box, then you could take long-lived mutable references and not have to clone anything at all. But RefCell’s borrow is inherently short lived.)