Deleting node from tree

help
1

So I have this code

Which is this

pub struct Tree {
    pub left: Option<Box<Tree>>,
    pub right: Option<Box<Tree>>,
    handle: u64,
}

impl Tree {
    pub fn remove_from_tree(&mut self, handle: u64) -> bool {
        // looks in some data in self to determine if it should be deleted
        // or not, then returns true to tell the parent to delete it
        
        if self.handle == handle {
            return true;
        }

        if let Some(ref mut split) = self.left {
                if Self::remove_from_tree(split, handle) {
                    self.left = None;
                }
            }

            if let Some(ref mut split) = self.right {
                if Self::remove_from_tree(split, handle) {
                    self.right = None;
                }
            }

        false
      }
}

And I get this error

<anon>:18:17: 18:33 error: cannot assign to `self.left` because it is borrowed [E0506]
<anon>:18                 self.left = None;
                          ^~~~~~~~~~~~~~~~
<anon>:16:21: 16:34 note: borrow of `self.left` occurs here
<anon>:16         if let Some(ref mut split) = self.left {
                              ^~~~~~~~~~~~~

I can likely do some (bad) workaround to get around this but I'm wonder if anyone has some suggestion how in general to deal with this case?

Cheers!

2 Likes
2

I see two easy workarounds:

if let Some(mut split) = self.right.take() {
    if !split.remove_from_tree(handle) {
        self.right = Some(split);
    }
}

and

let mut remove = false;
if let ... { remove = true; }
if remove { self.left = None; }

There is also an ownership-consuming version:

    pub fn remove_from_tree(mut self: Box<Tree>, handle: u64) -> Option<Box<Self>> {
        if self.handle == handle { return None; }
        self.left = self.left.take().and_then(|v| v.remove_from_tree(handle));
        self.right = self.right.take().and_then(|v| v.remove_from_tree(handle));
        Some(self)
    }

or even

    pub fn remove_from_tree(self: Tree, handle: u64) -> Option<Box<Self>> {
        if self.handle == handle {
            None
        } else {
            let left = self.left.and_then(|v| v.remove_from_tree(handle));
            let right = self.right.and_then(|v| v.remove_from_tree(handle));
            Some(Box::new(Tree { left: left, right: right, handle: self.handle }))
        }
    }
3 Likes
3

Thanks!

One question: Won't the last version cause quite a bit of extra allocations?

4

Probably, yes. It's what you would write in a pure functional language (I think), and there the compiler would be expected to optimize that away :slight_smile:

5

Ah yeah :slight_smile: Don't think the compiler will optimize it away in this case but I must say the last version looks elegant. Seems I need to upgrade my Rust-fu when it comes to using take/and_then() etc :slight_smile:

6

What about using .as_mut().map(...), like this?

if self.left.as_mut().map(|split| split.remove_from_tree(handle)).unwrap_or(false) {
    self.left = None;
}

(may need some formatting)

Full code: Rust Playground

2 Likes
7

Neat! Thanks :slight_smile: