Rust binary tree insert implementation difficulty

Question

I have looked at many topics, but I could not find any clue as to why my code won't compile (except for an issue with ownership of course), hopefully someone here can help me.

I am working on a binary tree implementation, and one of its functions is the insert function. This is my first time coding in Rust, and although I have looked at the documentation many times, I cannot figure out what is wrong with the ownership in the following code (I only posted, I hope, all relevant code):

#[derive(Debug)]
struct Data {
    name: String,
    age: i32,
}

#[derive(Debug)]
struct Node {
    value: Data,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

pub struct SortedContainer {
    root: Option<Box<Node>>,
}

impl SortedContainer {
    pub fn insert(&mut self, name: String, age: i32) {
        let d = Data {
            name: name,
            age: age,
        };
        let n = Node {
            value: d,
            left: None,
            right: None,
        };
        match self.root {
            Some(ref rootnode) => SortedContainer::node_insert(n, *rootnode),
            None => self.root = Some(Box::new(n)),
        }
    }
    fn node_insert(n: Node, mut n2: Box<Node>) {
        let i = SortedContainer::data_compare(&n.value, &n2.value);
        if i < 0 {
            match n2.right {
                Some(ref rightnode) => SortedContainer::node_insert(n, *rightnode),
                None => n2.right = Some(Box::new(n)),
            }
        } else if i > 0 {
            match n2.left {
                Some(ref leftnode) => SortedContainer::node_insert(n, *leftnode),
                None => n2.left = Some(Box::new(n)),
            }
        }
    }
    fn data_compare(d: &Data, d2: &Data) -> i32 {
        if d.age < d2.age {
            return -1;
        } else if d.age > d2.age {
            return 1;
        } else if d.name == d2.name {
            return 0;
        } else if d.name > d2.name {
            return 1;
        } else if d.name < d2.name {
            return -1;
        } else {
            return 0;
        }
    }
}

The error that the terminal provides is:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:31:67
   |
31 |             Some(ref rootnode) => SortedContainer::node_insert(n, *rootnode),
   |                                                                   ^^^^^^^^^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:39:72
   |
39 |                 Some(ref rightnode) => SortedContainer::node_insert(n, *rightnode),
   |                                                                        ^^^^^^^^^^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:44:71
   |
44 |                 Some(ref leftnode) => SortedContainer::node_insert(n, *leftnode),
   |                                                                       ^^^^^^^^^ cannot move out of borrowed content

Has it got something to do with the Box or with the left/right allocation?

Answer 1

You are trying to move your boxed nodes out of their enclosing options. This is not allowed, because the options will still be owned by the corresponding parent nodes afterwards. You could theoretically call take on the options to move the nodes. take moves the value out of the option and replaces it with None instead of leaving it "empty" (not allowed).

However, this would effectively detach the child nodes from their respective parent node. You would have to reattach them after returning from inserting the new node:

fn node_insert(n: Node, mut n2: Box<Node>) -> Box<Node>{
    let i = SortedContainer::data_compare(&n.value, &n2.value);
    if i < 0 {
        n2.right = match n2.right.take() {
            Some(rightnode) => Some(SortedContainer::node_insert(n, rightnode)),
            None => Some(Box::new(n)),
        }
    } else if i > 0 {
        n2.left = match n2.left.take() {
            Some(leftnode) => Some(SortedContainer::node_insert(n, leftnode)),
            None => Some(Box::new(n)),
        }
    }
    n2
}

same for the root node:

self.root = match self.root.take() {
    Some(rootnode) => Some(SortedContainer::node_insert(n, rootnode)),
    None => Some(Box::new(n)),
}

An alternative solution involves passing mutable references to the nodes instead of moving them. This works, because you actually only need to mutate the nodes along the path from the root node to the leaf node where the new node should be inserted:

fn node_insert(n: Node, n2: &mut Node) {
    let i = SortedContainer::data_compare(&n.value, &n2.value);
    if i < 0 {
        match n2.right {
            Some(ref mut rightnode) => SortedContainer::node_insert(n, rightnode),
            None => n2.right = Some(Box::new(n)),
        }
    } else if i > 0 {
        match n2.left {
            Some(ref mut leftnode) => SortedContainer::node_insert(n, leftnode),
            None => n2.left = Some(Box::new(n)),
        }
    }
}

same for the root node:

match self.root {
    Some(ref mut rootnode) => SortedContainer::node_insert(n, rootnode),
    None => self.root = Some(Box::new(n)),
}