I want to create a binary tree through a series of insertions. Each insertion is provided with an list of u8
and a value. The list of u8
represents left or right while descending the tree: 0 is for left, not 0 for right.
While there are a number of examples of Rust binary trees, I haven't come upon one which inserts through a loop instead of recursively. I've come to and become stuck at the following (playground):
pub struct Tree {
data: u8,
left: Option<Box<Tree>>,
right: Option<Box<Tree>>,
}
impl Tree {
fn new() -> Self {
Tree {
data: 0,
left: None,
right: None,
}
}
fn insert(&mut self, code: &[u8], data: u8) {
let mut tree = self;
for i in code {
match i {
0 => {
if tree.left.is_none() {
tree.left = Some(Box::new(Tree::new()));
}
tree = &mut tree.left.as_mut().unwrap(); // <---
}
_ => {
if tree.right.is_none() {
tree.right = Some(Box::new(Tree::new()));
}
tree = &mut tree.right.unwrap(); // <---
}
}
}
tree.data = data;
}
}
I'm stuck at the two locations identified where I try to assign tree
iteratively as I descend:
error[E0597]: borrowed value does not live long enough
--> src/main.rs:24:33
|
24 | tree = &mut tree.left.as_mut().unwrap();
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^- temporary value dropped here while still borrowed
| |
| temporary value does not live long enough
...
35 | }
| - temporary value needs to live until here
|
= note: consider using a `let` binding to increase its lifetime
error[E0597]: borrowed value does not live long enough
--> src/main.rs:30:33
|
30 | tree = &mut tree.right.unwrap();
| ^^^^^^^^^^^^^^^^^^^- temporary value dropped here while still borrowed
| |
| temporary value does not live long enough
...
35 | }
| - temporary value needs to live until here
|
= note: consider using a `let` binding to increase its lifetime
error[E0507]: cannot move out of borrowed content
--> src/main.rs:30:33
|
30 | tree = &mut tree.right.unwrap();
| ^^^^ cannot move out of borrowed content
error[E0502]: cannot borrow `tree.left` as immutable because it is also borrowed as mutable
--> src/main.rs:21:24
|
21 | if tree.left.is_none() {
| ^^^^^^^^^ immutable borrow occurs here
...
24 | tree = &mut tree.left.as_mut().unwrap();
| --------- mutable borrow occurs here
...
35 | }
| - mutable borrow ends here
error[E0506]: cannot assign to `tree.left` because it is borrowed
--> src/main.rs:22:25
|
22 | tree.left = Some(Box::new(Tree::new()));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `tree.left` occurs here
23 | }
24 | tree = &mut tree.left.as_mut().unwrap();
| --------- borrow of `tree.left` occurs here
error[E0506]: cannot assign to `tree` because it is borrowed
--> src/main.rs:24:21
|
24 | tree = &mut tree.left.as_mut().unwrap();
| ^^^^^^^^^^^^---------^^^^^^^^^^^^^^^^^^
| | |
| | borrow of `tree` occurs here
| assignment to borrowed `tree` occurs here
error[E0499]: cannot borrow `tree.left` as mutable more than once at a time
--> src/main.rs:24:33
|
24 | tree = &mut tree.left.as_mut().unwrap();
| ^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
35 | }
| - mutable borrow ends here
error[E0506]: cannot assign to `tree` because it is borrowed
--> src/main.rs:30:21
|
24 | tree = &mut tree.left.as_mut().unwrap();
| --------- borrow of `tree` occurs here
...
30 | tree = &mut tree.right.unwrap();
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `tree` occurs here
What is the right way to go about this?