Binary tree implementation (beginner)

[LouisWatermeyer]

Hi,
i tried to implement a binary tree as an exercise to get started with Rust and get some familliarity with Option, Box and Result.

I am unhappy however, because the resulting structure is not easy to use.

I am looking for hints to make the 'api' better, whether i used the Option and Result correctly (or is it needlessly complicating things) and general rust tips.

Thank you for any feedback.

Edit: depth is not implemented correctly, I know

pub struct BinaryTree<T> {
    root: BinaryNode<T>,
    depth: i32,
}

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

    pub fn root(&self) -> &BinaryNode<T> {
        &self.root
    }

    pub fn root_mut(&mut self) -> &mut BinaryNode<T> {
        &mut self.root
    }

    pub fn depth(&self) -> i32 {
        self.depth
    }
}

pub struct BinaryNode<T> {
    value: Option<T>,
    left: Box<Option<BinaryNode<T>>>,
    right: Box<Option<BinaryNode<T>>>,
}

impl<T> BinaryNode<T> {
    pub fn new() -> Self {
        BinaryNode {
            value: None,
            left: Box::new(None),
            right: Box::new(None),
        }
    }

    pub fn from_value(value: T) -> Self {
        BinaryNode {
            value: Some(value),
            left: Box::new(None),
            right: Box::new(None),
        }
    }

    pub fn value(&self) -> &Option<T> {
        &self.value
    }

    pub fn is_filled(&self) -> bool {
        self.value.is_some()
    }

    pub fn left(&self) -> &Option<BinaryNode<T>> {
        &(*(self.left)) // WTF is there a better way?
                        // * derefs the Box resulting in an Option<BinaryNode<T>>   ? unsure
                        // & provides the reference to that derefed thing.          ? unsure
    }

    pub fn right(&self) -> &Option<BinaryNode<T>> {
        &(*(self.right)) // WTF is there a better way?
                         // * derefs the Box resulting in an Option<BinaryNode<T>>  ? unsure
                         // & provides the reference to that derefed thing.         ? unsure
    }

    // Appends a new child node to the left containing the given Value.
    // This will fail if the node already has a left child. Use set_left instead to replace an existing child node.
    // If the action is successfull, Result will conatin a reference to the new child node.
    pub fn append_left(&mut self, value: T) -> Result<&Option<BinaryNode<T>>, String> {
        if self.left.is_none() {
            self.left = Box::new(Some(BinaryNode::from_value(value)));
            Ok(self.left())
        } else {
            Err(String::from(
                "Can not create a new child node in left, because left is not empty.",
            ))
        }
    }

    // Appends a new child node to the right containing the given Value.
    // This will fail if the node already has a right child. Use set_right instead to replace an existing child node.
    // If the action is successfull, Result will conatin a reference to the new child node.
    pub fn append_right(&mut self, value: T) -> Result<&Option<BinaryNode<T>>, String> {
        if self.right.is_none() {
            self.right = Box::new(Some(BinaryNode::from_value(value)));
            Ok(self.right())
        } else {
            Err(String::from(
                "Can not create a new child node in right, because right is not empty.",
            ))
        }
    }

    pub fn clear_left(&mut self) -> Option<BinaryNode<T>> {
        let old_left = self.left.take();
        self.left = Box::new(None);
        old_left
    }

    pub fn clear_right(&mut self) -> Option<BinaryNode<T>> {
        let old_right = self.right.take();
        self.right = Box::new(None);
        old_right
    }

    // Replaces the child to the left.
    // Returns the old child.
    pub fn set_left(&mut self, new_node: BinaryNode<T>) -> Option<BinaryNode<T>> {
        let old_left = self.left.take();
        self.left = Box::new(Some(new_node));
        old_left
    }

    // Replaces the child to the right.
    // Returns the old child.
    pub fn set_right(&mut self, new_node: BinaryNode<T>) -> Option<BinaryNode<T>> {
        let old_right = self.right.take();
        self.right = Box::new(Some(new_node));
        old_right
    }
}

#[cfg(test)]
mod tests {

    use super::*;

    #[test]
    fn test_stuff() {
        let mut tree: BinaryTree<i32> = BinaryTree::new();

        // A newly created tree can not have a root value
        assert!(!tree.root().is_filled());

        // A newly created trees root can not have any children
        assert!(tree.root().left().is_none());
        assert!(tree.root().right().is_none());

        // Fill the tree a bit
        assert!(tree.root_mut().append_left(2).is_ok());
        assert!(tree.root_mut().append_right(3).is_ok());

        // Check if the tree was filled correctly
        assert_eq!(tree.root().left().as_ref().unwrap().value().unwrap(), 2); // 🤮
        assert_eq!(tree.root().right().as_ref().unwrap().value().unwrap(), 3); // 🤮

        // Clear some part of the tree
        assert_eq!(tree.root_mut().clear_left().unwrap().value().unwrap(), 2);
        assert_eq!(tree.root_mut().clear_right().unwrap().value().unwrap(), 3);
        assert!(tree.root().left().is_none());
        assert!(tree.root().right().is_none());

        // Set some new children. Expect the old node is returned.
        assert!(tree.root_mut().set_left(BinaryNode::from_value(4)).is_none());
        assert_eq!(tree.root().left().as_ref().unwrap().value().unwrap(), 4);
        assert!(tree.root_mut().set_right(BinaryNode::from_value(5)).is_none());
        assert_eq!(tree.root().right().as_ref().unwrap().value().unwrap(), 5);

        assert!(tree.root_mut().set_left(BinaryNode::from_value(6)).is_some_and(|node| node.value().unwrap() == 4));
        assert_eq!(tree.root().left().as_ref().unwrap().value().unwrap(), 6);
        assert!(tree.root_mut().set_right(BinaryNode::from_value(7)).is_some_and(|node| node.value().unwrap() == 5));
        assert_eq!(tree.root().right().as_ref().unwrap().value().unwrap(), 7);
    }
}

[gretchenfrage]

Wooo! Welcome! Some thoughts.

Putting this on play.rust-lang.org since it's a large snippet and that makes it runnable: Rust Playground

For both structs, you can #[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]

Actually, instead of deriving Default, you should implement it manually, and make it just call Self::new(). If you derive Default it will make it implement Default only where T implements Default, but since T is wrapped in an Option that bound isn't actually necessary.

Similarly, you can implement From<T> for BinaryNode and delegate to Self::from_value.

Also, instead of deriving Debug, you may want to manually implement it with Formatter::debug_map so it prints like a map rather than like a tree, if that's how you want it to print. That's what the stdlib btreemap stuff does.

^-- if and when you actually start enforcing map invariants like keys being unique and the tree being overall sorted

You should change Box<Option<...>> to Option<Box<..>>. That way you don't need to make a heap allocation if it's None. Plus, then you take advantage of the null pointer optimization.

IMO you should replace &Option<...> with Option<&...>. There's nothing you can do with the former you can't do with the latter, and with less API friction sometimes. You can perform the conversion where necessary with .as_ref().

[quinedot]

After changing Box<Option<_>> to Option<Box<_>>, and the API to return Option<&_>, some WTFs go away:

    pub fn left(&self) -> Option<&BinaryNode<T>> {
        self.left.as_deref()
    }

    pub fn right(&self) -> Option<&BinaryNode<T>> {
        self.right.as_deref()
    }

(I didn't attempt to make them nicer without the changes.)

I changed append_left and append_right to return Result<&BinaryNode<T>, _>. You can unwrap without worrying about panics since you know it's not None.

You don't have to create new boxes in clear_left and clear_right. Since I changed the layout, I rewrote these anyway. They could return Box<_> instead to maybe avoid extra work, but at the cost of leaking implementation details (albeit not surprising ones). set_left and set_right were similarly rewrote.

I also made value return Option<&_> and rewrote the tests to use more Option mappers and compare things like Some(&4). Same length but hopefully less ?

-assert_eq!(tree.root().left().as_ref().unwrap().value().unwrap(), 2); // 🤮
+assert_eq!(tree.root().left().and_then(BinaryNode::value), Some(&2));

This could be shorter instead if you implemented PartialEq<T> for BinaryNode<T> and so on.

assert_eq!(tree.root().left().unwrap(), &2);

Rust Playground

---

There's some amount of overlap between writing a binary tree and writing a linked list, so you might want to read this well-known book.