Cannot borrow node as mutable more than once while implementing a binary search tree

Question

I'm trying to implement a binary search tree in Rust and I am running into problems with inserting an element. What is an idiomatic way of doing this in Rust?

Here is my implementation:

use std::cmp::Ordering;

pub struct BinarySearchTree {
    root: OptNode,
    size: u32,
}

type OptNode = Option<Box<Node>>;

struct Node {
    key: i32,
    left: OptNode,
    right: OptNode,
}

impl BinarySearchTree {
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            size: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn size(&self) -> u32 {
        self.size
    }

    pub fn contains(&self, key: i32) -> bool {
        let mut node = &self.root;
        while let Some(ref boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &boxed_node.left,
                Ordering::Greater => node = &boxed_node.right,
                Ordering::Equal => return true,
            }
        }

        false
    }

    pub fn insert(&mut self, key: i32) {
        let mut node = &mut self.root;
        while let Some(ref mut boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &mut boxed_node.left,
                Ordering::Greater => node = &mut boxed_node.right,
                Ordering::Equal => return,
            }
        }

        *node = Some(Box::new(Node {
            key: key,
            left: None,
            right: None,
        }));
    }
}

fn main() {}

Here are the errors I'm getting:

error[E0499]: cannot borrow `node.0` as mutable more than once at a time
  --> src/main.rs:47:24
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ^^^^^^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
60 |     }
   |     - mutable borrow ends here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:49:35
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ------------------ borrow of `node` occurs here
48 |             match key.cmp(&boxed_node.key) {
49 |                 Ordering::Less => node = &mut boxed_node.left,
   |                                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `node` because it is borrowed
  --> src/main.rs:50:38
   |
47 |         while let Some(ref mut boxed_node) = *node {
   |                        ------------------ borrow of `node` occurs here
...
50 |                 Ordering::Greater => node = &mut boxed_node.right,
   |                                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `node` occurs here

error[E0506]: cannot assign to `*node` because it is borrowed
  --> src/main.rs:55:9
   |
47 |           while let Some(ref mut boxed_node) = *node {
   |                          ------------------ borrow of `*node` occurs here
...
55 | /         *node = Some(Box::new(Node {
56 | |             key: key,
57 | |             left: None,
58 | |             right: None,
59 | |         }));
   | |___________^ assignment to borrowed `*node` occurs here

Abracadabra

Answer 1

Rust's compiler isn't sophisticated enough (yet?) to handle this situation. Rust sees that you're trying to borrow the same value mutably more than once, because it sees a repeated mutable borrow on the same variable in a loop. Of course, that's not what you're trying to do, as you want to reassign the variable on each iteration, but Rust doesn't support assigning to a variable that's being borrowed.

What we need to do instead is have intermediate variables so that the compiler can track the borrows correctly. How do we create an indeterminate amount of variables? With recursion!

impl BinarySearchTree {
    pub fn insert(&mut self, key: i32) {
        fn insert_node(node: &mut OptNode, key: i32) {
            if let Some(ref mut boxed_node) = *node {
                match key.cmp(&boxed_node.key) {
                    Ordering::Less => insert_node(&mut boxed_node.left, key),
                    Ordering::Greater => insert_node(&mut boxed_node.right, key),
                    Ordering::Equal => return,
                }
            } else {
                *node = Some(Box::new(Node { key: key, left: None, right: None}));
            }
        }

        insert_node(&mut self.root, key)
    }
}

Note: although this algorithm is tail-recursive, Rust doesn't optimize this into tail calls, so it could cause a stack overflow in degenerate cases.

Dilation

Thanks! Is there a way to do it which is not recursive? – Abracadabra

Answer 2

Without recursion:

pub fn insert(&mut self, key: i32) {
    let mut node = &mut self.root;
    loop {
        node = match node.as_ref().map(|n| key.cmp(&n.key)) {
            Some(Ordering::Less) => &mut { node }.as_mut().unwrap().left,
            Some(Ordering::Equal) => return,
            Some(Ordering::Greater) => &mut { node }.as_mut().unwrap().right,
            None => {
                *node = Some(Box::new(Node {
                    key: key,
                    left: None,
                    right: None,
                }));
                return;
            }
        };
    }
}

The unwrap() is safe here.

Could you please elaborate on why {node}.as_mut()... works

node is a mutable reference (&mut Option<Box<Node>>). It can not be copied.

let temp = node;

Here node was moved into temp. This is exactly what we need to avoid assigning to the borrowed node. We can move node to the new temporary variable and borrow it.

// ...
Some(Ordering::Less) => {
    let temp = node;
    &mut temp.as_mut().unwrap().left
}
// ...

Compact notation:

// ...
Some(Ordering::Less) =>  &mut { let temp = node; temp }.as_mut().unwrap().left,
// ...

The expressions { node } and { let temp = node; temp } are equivalent, but in the first case the node moves to an implicit temporary variable.

Immortelle

Could you please elaborate on why {node}.as_mut()... works, but node.as_mut()... ends up in borrowing errors? – Pierian

Answer 3

As Francis Gagné said

Rust's compiler isn't sophisticated enough (yet?)

That sophistication is coming, and it's called non-lexical lifetimes. With them enabled, your original code works as-is:

#![feature(nll)]

use std::cmp::Ordering;

pub struct BinarySearchTree {
    root: OptNode,
    size: u32,
}

type OptNode = Option<Box<Node>>;

struct Node {
    key: i32,
    left: OptNode,
    right: OptNode,
}

impl BinarySearchTree {
    pub fn new() -> Self {
        BinarySearchTree {
            root: None,
            size: 0,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.size == 0
    }

    pub fn size(&self) -> u32 {
        self.size
    }

    pub fn contains(&self, key: i32) -> bool {
        let mut node = &self.root;
        while let Some(ref boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &boxed_node.left,
                Ordering::Greater => node = &boxed_node.right,
                Ordering::Equal => return true,
            }
        }

        false
    }

    pub fn insert(&mut self, key: i32) {
        let mut node = &mut self.root;
        while let Some(ref mut boxed_node) = *node {
            match key.cmp(&boxed_node.key) {
                Ordering::Less => node = &mut boxed_node.left,
                Ordering::Greater => node = &mut boxed_node.right,
                Ordering::Equal => return,
            }
        }

        *node = Some(Box::new(Node {
            key: key,
            left: None,
            right: None,
        }));
    }
}

fn main() {}

Yttria