# Another binary tree experiment

Hi,
it seems there are already several other binary search tree problems but mine seems different.
I had my tree working fine so far until I decided to get away from recursive functions. As tree is still unbalanced it might end up looking like a linked list so I thought it unwise to use recursion.
It all works fine until I tried to make my insert function non recursive:

``````type SubNode<K, V> = Option<Box<TreeNode<K, V>>>;

#[derive(Debug)]
struct TreeNode<K: PartialOrd + Debug, V: Clone> {
key: K,
value: V,
smaller: SubNode<K, V>,
bigger: SubNode<K, V>,
}

impl<K, V> TreeNode<K, V>
where
K: PartialOrd + Debug,
V: Clone,
{
fn new(key: K, value: V) -> TreeNode<K, V> {
TreeNode {
key,
value,
smaller: None,
bigger: None,
}
}
}

pub struct BTree<'a, K: PartialOrd + Debug, V: Clone> {
root: SubNode<K, V>,
}

impl<'a, K, V> BTree<'a, K, V>
where
K: PartialOrd + Debug,
V: Clone,
{
pub fn new() -> BTree<'a, K, V> {
BTree {
root: None,
}
}

pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if let Some(node) = &mut self.root {
let mut curr = node;
loop {
if key < curr.key {
if let Some(node) = &mut curr.smaller {
curr = node;
} else {
// kaboom !
curr.smaller = Some(Box::new(TreeNode::new(key, value)));
return None;
}
} else if key > curr.key {
if let Some(node) = &mut curr.bigger {
curr = node;
} else {
// kaboom !
curr.bigger = Some(Box::new(TreeNode::new(key, value)));
return None;
}
} else {
return Some(std::mem::replace(&mut curr.value, value));
}
}
} else {
self.root = Some(Box::new(TreeNode::new(key, value)));
None
}
}
}

``````

Unfortunately rust does not like that:

``````cargo build
Compiling rust_tree v0.1.0 (/home/thomas/develop/rust/rust_tree)
error[E0506]: cannot assign to `curr.smaller` because it is borrowed
--> src/tree/binary_tree.rs:32:25
|
29 |                     if let Some(node) = &mut curr.smaller {
|                                         ----------------- borrow of `curr.smaller` occurs here
...
32 |                         curr.smaller = Some(Box::new(TreeNode::new(key, value)));
|                         ^^^^^^^^^^^^
|                         |
|                         assignment to borrowed `curr.smaller` occurs here
|                         borrow later used here

error[E0506]: cannot assign to `curr.bigger` because it is borrowed
--> src/tree/binary_tree.rs:39:25
|
36 |                     if let Some(node) = &mut curr.bigger {
|                                         ---------------- borrow of `curr.bigger` occurs here
...
39 |                         curr.bigger = Some(Box::new(TreeNode::new(key, value)));
|                         ^^^^^^^^^^^
|                         |
|                         assignment to borrowed `curr.bigger` occurs here
|                         borrow later used here

error: could not compile `rust_tree` due to 2 previous errors
``````

Apparently rust does not get that the curr var has been overwritten and the &mut to curr.smaller / curr.bigger are thus voided. I have tried all sorts of variations but it always ends up with the same type of problem. Any ideas how to work around this ?

Cheers Thomas

Can you "fix" this playground version of your code to match your error?

I think the problem here is that `curr = node` establishes that the lifetime of the `node` loan, which comes with `&mut curr.smaller`, must cover the entire scope of `curr`, so the borrow checker unnecessarily treats it as if you wrote `let curr = &mut curr.smaller` at the top of the function. `&mut` is exclusive, so once it's borrowed in one place, it can't be used anywhere else. It seems like a limitation of the lifetime analysis, because the code should be fine due to the `return`.

Maybe `curr.smaller.get_or_insert_with()` will work?

This compiles with the error that I stumble over

Yeah, that is pretty much how I see it too. I did consider using some of the methods of Option including get_or_insert() but I did not see how that will do the job. I tried several variations of the algorithm but always got stuck with the same problem. The only version that does the job is the recursive version but that can't be it. There must be a way to code this in rust without using recursion.

``````    pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if let Some(node) = &mut self.root {
let mut curr = node;
loop {
if key < curr.key {
match &mut curr.smaller {
Some(node) => curr = node,
s @ None => {*s = Some(Box::new(TreeNode::new(key, value)));return None;}
}
} else if key > curr.key {
match &mut curr.bigger {
Some(node) => curr = node,
s @ None => {*s = Some(Box::new(TreeNode::new(key, value)));return None;}
}
} else {
return Some(std::mem::replace(&mut curr.value, value));
}
}
} else {
self.root = Some(Box::new(TreeNode::new(key, value)));
None
}
}
``````

Thanks, that seems to do the job, it compiles OK and survives the tests so it seems to work. I cannot say that I have seen / understand that syntax before though. I better read up about it..

The original error is due to NLL problem case #3. It compiles with the next-gen borrow checker (Polonius).

(In the meanwhile, workarounds are required.)

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.