2

Rust playground link to code and tests

I am writing a function that takes in the root of a binary tree. It should return the right-most value in the bottom most level of the tree.


/// Represents a binary tree
/// The criteria for binary tree
/// a) has at most 2 children
/// b) exactly 1 root
/// c) exactly 1 path between root
///    and any node
#[derive(Debug, Clone)]
pub struct TreeNode {
    val: i32,
    left: Option<TreeNodeRef>,
    right: Option<TreeNodeRef>,
}

type TreeNodeRef = Rc<RefCell<TreeNode>>;

This is the function:

///        -1
///      /    \
///    -6     -5
///   /  \      \
/// -3   -4    -13
///     / \    /    
///    -2  6  7
/// Then the right-most value in the bottom-most
/// level is 7
pub fn bottom_right_value(root: TreeNodeRef) -> i32 {
    // `Rc.clone()` is cheap so use
    let mut current = root.clone();
    let mut queue: VecDeque<TreeNodeRef> = VecDeque::new();
    queue.push_back(root);
    while !queue.is_empty() {
        current = queue.pop_front().unwrap();

        if let Some(left) = &current.borrow().left {
            queue.push_back(left.clone());
        };
        if let Some(right) = &current.borrow().right {
            queue.push_back(right.clone());
        };
    }
   
    current.borrow().val
}

However, the borrow checker seems to think that the current does not live long enough. I get the following error:

Checking tree_bottom_right_value v0.1.0 (/Users/tesseract/01-programming/01-Rust/01-Learn/14-data-structures/tree_bottom_right_value)
error[E0597]: `current` does not live long enough
  --> src/lib.rs:50:5
   |
37 |     let mut current = root.clone();
   |         ----------- binding `current` declared here
...
50 |     current.borrow().val
   |     ^^^^^^^^^^^^^^^^
   |     |
   |     borrowed value does not live long enough
   |     a temporary with access to the borrow is created here ...
51 | }
   | -
   | |
   | `current` dropped here while still borrowed
   | ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `Ref<'_, TreeNode>`
   |
   = 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
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
   |
50 |     let x = current.borrow().val; x
   |     +++++++                     +++

If I follow the recommendation and change the last line of the function to:

    let result = current.borrow().val;
    result

The error goes away and everything works. Why does binding to a let make the code work? With current.borrow().val, I'm trying to return the i32 val, but the compiler doesn't like it, but allows it if you bind it to a variable. It seems strange to me.

E_net4
  • 27,810
  • 13
  • 101
  • 139
Anup
  • 951
  • 2
  • 10
  • 25
  • 2
    Why don't you use `Option>`? You don't need shared ownership. Trees work well in Rust. – Chayim Friedman Feb 23 '23 at 07:28
  • This is probably the same as in [this answer](https://stackoverflow.com/a/50570026/5397009): it is a known limitation of the current borrow-checker, that should be fixed with polonius (available on nightly with `RUSTFLAGS="-Zpolonius"`). – Jmb Feb 23 '23 at 07:28
  • 1
    @Jmb It does not work with Polonius, so this is not the answer. – Chayim Friedman Feb 23 '23 at 07:31
  • Minimal example: `pub fn bottom_right_value(root: TreeNodeRef) -> i32 { let current = root; current.borrow().val }`. Strangely it does not error if we remove `current`. – Chayim Friedman Feb 23 '23 at 07:35
  • Fun fact: it also works if you explicitly write `return current.borrow().val;`: [playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=00f839fedf5c95d8a4c8f6607a043b2a) – Jmb Feb 23 '23 at 07:38
  • 2
    More fun fact: if you write `return current.borrow().val` without the semicolon it still errors. Which makes me believe this is related to expressions. This smells like a bug in the compiler, however. – Chayim Friedman Feb 23 '23 at 07:42
  • I tend to agree that this might be a compiler bug. I tried to reproduce it in other ways, and it seems to happen very spuriously. If someone wants to report it, this is one possible MRE: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=29c98c8ba268911a93933da64cc2d264 – Finomnis Feb 23 '23 at 09:13
  • So, this is a compiler bug, then? – Anup Feb 23 '23 at 20:54
  • I would report it. – Chayim Friedman Feb 24 '23 at 09:50

0 Answers0