0

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?

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • 1
    I believe your question is answered by the answers of [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time](https://stackoverflow.com/q/37986640/155423). If you disagree, please [edit] your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Jun 30 '18 at 16:07
  • [The duplicate applied to your question](http://play.rust-lang.org/?gist=57ccdf73ad9c94d80e2607e3b95cea20&version=stable&mode=debug&edition=2015). – Shepmaster Jun 30 '18 at 16:15

0 Answers0