Tree Traversal without raw pointer

[changhe3]

A simple binary search tree can be written in rust using box only without unsafe like this:

pub struct BinaryTree<T> {
    root: SubTree<T>,
    len: usize,
}

struct Node<T> {
    elem: T,
    left: SubTree<T>,
    right: SubTree<T>,
}

type SubTree<T> = Option<Box<Node<T>>>;

impl<T> BinaryTree<T>  {
    pub fn new() -> Self {
        BinaryTree {
            root: None,
            len: 0,
        }
    }
}

However to insert a node, I wrote the following code

impl <T: Ord> BinaryTree<T> {
    pub fn insert(&mut self, value: T) -> bool {
        let mut subtree = &mut self.root;
        while let Some(node) = subtree.as_mut() {
            subtree = match value.cmp(&node.elem) {
                Ordering::Equal => { return false; }
                Ordering::Less => &mut node.left,
                Ordering::Greater => &mut node.right,
            }
        }

        *subtree = Box::new(Node { elem: value, left: None, right: None }).into();
        self.len += 1;
        true
    }
}

which won't pass the borrow checker. However this code passes:

impl <T: Ord> BinaryTree<T> {
    pub fn insert(&mut self, value: T) -> bool {
        let mut subtree = &mut self.root;
        while let Some(ref mut node) = subtree {
            subtree = match value.cmp(&node.elem) {
                Ordering::Equal => { return false; }
                Ordering::Less => &mut node.left,
                Ordering::Greater => &mut node.right,
            }
        }

        *subtree = Box::new(Node { elem: value, left: None, right: None }).into();
        self.len += 1;
        true
    }
}

Why is the use of ref mut mandatory here?

[jofas]

Because if you bind a variable in a pattern, it is using move or copy semantics per default. You can override this with the ref or ref mut keywords so that the variable binds to a (mutable) reference of the value instead. From the reference:

By default, identifier patterns bind a variable to a copy of or move from the matched value depending on whether the matched value implements Copy. This can be changed to bind to a reference by using the ref keyword, or to a mutable reference using ref mut.

---

Edit: Note that if you remove the as_mut call on subtree, you also don't need ref mut, as your subtree is a reference pattern. When binding to reference patterns, ref [mut] can be omitted, as it is implicitly added by the compiler:

use std::cmp::Ordering;

pub struct BinaryTree<T> {
    root: SubTree<T>,
    len: usize,
}

struct Node<T> {
    elem: T,
    left: SubTree<T>,
    right: SubTree<T>,
}

type SubTree<T> = Option<Box<Node<T>>>;

impl<T> BinaryTree<T>  {
    pub fn new() -> Self {
        BinaryTree {
            root: None,
            len: 0,
        }
    }
}

impl <T: Ord> BinaryTree<T> {
    pub fn insert(&mut self, value: T) -> bool {
        let mut subtree = &mut self.root;
        while let Some(node) = subtree {
            subtree = match value.cmp(&node.elem) {
                Ordering::Equal => { return false; }
                Ordering::Less => &mut node.left,
                Ordering::Greater => &mut node.right,
            }
        }

        *subtree = Box::new(Node { elem: value, left: None, right: None }).into();
        self.len += 1;
        true
    }
}

Playground.

[changhe3]

Thank you for your quick reply. On a separate note, what's exactly the reason that I cannot call subtree.as_mut() there? I also tried subtree.as_mut().take() which doesn't work either. Is it related to certain restrictions around mutable getters? I haven't used Rust for a while so things got a bit hazy for me...

[jofas]

@changhe3

On a separate note, what's exactly the reason that I cannot call subtree.as_mut() there?

I'm not exactly sure. When we bind the result of calling as_mut to its own variable and make types, implicit dereferencing and reborrows explicit (snippet below), the structure becomes a bit clearer. Inside the loop we assign subtree to a (splitting) reborrow from subtree_iter (which itself is a reborrow from subtree). Looks to me like you can't have cycles like that between two mutable variables reborrowing from each other.

use std::cmp::Ordering;

pub struct BinaryTree<T> {
    root: SubTree<T>,
    len: usize,
}

struct Node<T> {
    elem: T,
    left: SubTree<T>,
    right: SubTree<T>,
}

type SubTree<T> = Option<Box<Node<T>>>;

impl<T> BinaryTree<T> {
    pub fn new() -> Self {
        BinaryTree { root: None, len: 0 }
    }
}

impl<T: Ord> BinaryTree<T> {
    pub fn insert(&mut self, value: T) -> bool {
        let mut subtree: &mut Option<Box<Node<T>>> = &mut self.root;
        let mut subtree_iter: Option<&mut Box<Node<T>>> = Option::as_mut(&mut *subtree);

        while let Some(node) = subtree_iter {
            subtree = match Ord::cmp(&value, &(*node).elem) {
                Ordering::Equal => {
                    return false;
                }
                Ordering::Less => &mut (*node).left,
                Ordering::Greater => &mut (*node).right,
            };
            subtree_iter = Option::as_mut(&mut *subtree);
        }

        *subtree = Some(Box::new(Node {
            elem: value,
            left: None,
            right: None,
        }));
        self.len += 1;
        true
    }
}

Playground.

---

Edit: I think my assessment is correct, the cycle between subtree and subtree_iter is the problem. If we don't let subtree reborrow from subtree_iter inside of the loop, subtree_iter is not alive when we write to subtree after the loop:

use std::cmp::Ordering;

pub struct BinaryTree<T> {
    root: SubTree<T>,
    len: usize,
}

struct Node<T> {
    elem: T,
    left: SubTree<T>,
    right: SubTree<T>,
}

type SubTree<T> = Option<Box<Node<T>>>;

impl<T> BinaryTree<T> {
    pub fn new() -> Self {
        BinaryTree { root: None, len: 0 }
    }
}

impl<T: Ord> BinaryTree<T> {
    pub fn insert(&mut self, value: T) -> bool {
        let mut subtree: &mut Option<Box<Node<T>>> = &mut self.root;
        let mut subtree_iter: Option<&mut Box<Node<T>>> = Option::as_mut(&mut *subtree);

        while let Some(node) = subtree_iter {
            subtree = match Ord::cmp(&value, &(*node).elem) {
                Ordering::Equal => {
                    return false;
                }
                Ordering::Less => &mut subtree.as_mut().unwrap().left,
                Ordering::Greater => &mut subtree.as_mut().unwrap().right,
            };
            subtree_iter = Option::as_mut(&mut *subtree);
        }

        *subtree = Some(Box::new(Node {
            elem: value,
            left: None,
            right: None,
        }));
        self.len += 1;
        true
    }
}

Playground.

[quinedot]

I didn't really dig since a solution has already been presented, but it may be a version of this issue.