Borrowed value does not live long enough when adding to a binary tree built on RefCell

Question

I tried to implement an add operation in a binary tree:

use std::cell::RefCell;
use std::cmp::PartialOrd;

type Link<T> = RefCell<Option<Box<Node<T>>>>;

struct Node<T> {
    key: T,
    left: Link<T>,
    right: Link<T>,
}

struct Tree<T> {
    root: Link<T>,
}

impl<T> Node<T> {
    fn new(val: T) -> Self {
        Node {
            key: val,
            left: RefCell::new(None),
            right: RefCell::new(None),
        }
    }
}

impl<T: PartialOrd> Tree<T> {
    fn new() -> Self {
        Tree {
            root: RefCell::new(None),
        }
    }

    fn add(&self, val: T) {
        let mut next = self.root.borrow();
        let node = Box::new(Node::new(val));
        match next.as_ref() {
            None => {
                self.root.replace(Some(node));
                ()
            }
            Some(root_ref) => {
                let mut prev = root_ref;
                let mut cur: Option<&Box<Node<T>>> = Some(root_ref);
                while let Some(node_ref) = cur {
                    prev = node_ref;
                    if node.key < node_ref.key {
                        next = node_ref.left.borrow();
                    } else {
                        next = node_ref.right.borrow();
                    }
                    cur = next.as_ref();
                }
                if node.key < prev.key {
                    prev.left.replace(Some(node));
                } else {
                    prev.right.replace(Some(node));
                }
            }
        }
    }
}

fn main() {}

I don't understand why the next variable doesn't live long enough:

error[E0597]: `next` does not live long enough
  --> src/main.rs:36:15
   |
36 |         match next.as_ref() {
   |               ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `next` does not live long enough
  --> src/main.rs:51:27
   |
51 |                     cur = next.as_ref();
   |                           ^^^^ borrowed value does not live long enough
...
60 |     }
   |     - `next` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

next lives for the entire scope of the add function and, in my opinion, other variables containing references to it are dropped before next has dropped.

The compiler says that "values in a scope are dropped in the opposite order they are created", suggesting that there is another way to declare variables and to solve this problem, but I don't know how.

Answer 1

The problem I see is that in order to update a leaf node of your tree you have to hold a reference to each intermediate step, not only its parent, because all the links up to the root node must be kept alive while you are updating the value. And Rust lifetimes just cannot do that.

That is, Rust cannot do that in a loop, but it can do that in a recursive function, and a tree is best implemented with a recursive function.

Naturally, your recursive struct is Node, not Tree, but something like this could work (there are many ways to get the borrows to work):

impl<T: PartialOrd> Node<T> {
    fn add(&self, val: T) {
        let mut branch = if val < self.key {
            self.left.borrow_mut()
        } else {
            self.right.borrow_mut()
        };
        if let Some(next) = &*branch {
            next.add(val);
            return;
        }
        //Separated from the if let so that branch is not borrowed.
        *branch = Some(Box::new(Node::new(val)));
    }
}

And then, in impl Tree just relay the work to this one.

The code may be simplified a bit if, as other people noted, you get rid of the Tree vs Node and the RefCell...