Deleting node from tree


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;


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?



I see two easy workarounds:

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


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));

or even

    pub fn remove_from_tree(self: Tree, handle: u64) -> Option<Box<Self>> {
        if self.handle == handle {
        } 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 }))



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


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:


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:


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:


Neat! Thanks :slight_smile: