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) = ¤t.borrow().left {
queue.push_back(left.clone());
};
if let Some(right) = ¤t.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.