Roast my dumb BinaryTree implementation

51 points etzellux

Hi guys,
I'm a rust newbie. After finishing rustaceans I decided to try implementing a binary tree.
I struggled a lot trying to get the borrows right, and compiler screamed a lot at me especially when I tried to hold multiple mutable references (forgot they are exclusive). I managed to get it compiled but I'm not satisfied with the insert method as it looks kinda ugly and probably more complex than it should be, and I believe it's unidiomatic. I think a lot of that came from trying not to drop or move a Box, hence the \ref mut\\s. Could you mind giving me some guidance? What can i do to make this more idiomatic?

#[derive(Debug)]
pub struct Node<T> {
    pub value: T,
    pub left: Option<Box<Node<T>>>,
    pub right: Option<Box<Node<T>>>,
}


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


#[derive(Debug)]
pub struct BinaryTree<T> 
where T: PartialOrd {
    pub root: Option<Box<Node<T>>>
}

impl<T: PartialOrd> BinaryTree<T> {
    fn new() -> Self {
        BinaryTree { root: Option::None }
    }

    fn is_empty(&self) -> bool {
        return self.root.is_none();
    }

    fn insert(&mut self, value: T) {
        if let Some(ref mut node) = self.root {
            let mut node = node.as_mut();
            loop {
                if value < node.value {
                    if let Some(ref mut child) = node.left {
                        node = child.as_mut();
                    } else {
                        let new_node = Box::new(Node::new(value));
                        node.left = Some(new_node);
                        break;
                    }
                } else if value > node.value {
                    if let Some(ref mut child) = node.right {
                        node = child.as_mut();
                    } else {
                        let new_node = Box::new(Node::new(value));
                        node.right = Some(new_node);
                        break;
                    }
                } else {
                    break;
                }
            }
        } else {
            let new_node = Box::new(Node::new(value));
            self.root = Some(new_node);
        }
    }
} 


fn main() {
    let mut my_tree = BinaryTree::<i32>::new();
    my_tree.insert(5);
    my_tree.insert(7);
    my_tree.insert(3);
    my_tree.insert(10);

    println!("{:?}", my_tree);
}