Balanced Binary Tree in Rust

lib.rs

use std::collections::VecDeque;

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

impl<T> BinaryTree<T>
where
    T: Copy,
{
    pub fn new(value: T) -> Self {
        BinaryTree {
            value,
            left: None,
            right: None,
        }
    }

    pub fn left(mut self, node: BinaryTree<T>) -> Self {
        self.left = Some(Box::new(node));
        self
    }

    pub fn right(mut self, node: BinaryTree<T>) -> Self {
        self.right = Some(Box::new(node));
        self
    }

    pub fn insert(&mut self, new_value: T) {
        let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new();
        queue.push_front(self);

        loop {
            let BinaryTree {
                ref mut left,
                ref mut right,
                ..
            } = queue.pop_back().unwrap();

            match left {
                Some(node) => {
                    queue.push_front(node);
                }
                None => {
                    *left = Some(Box::new(BinaryTree::new(new_value)));
                    return;
                }
            }

            match right {
                Some(node) => {
                    queue.push_front(node);
                }
                None => {
                    *right = Some(Box::new(BinaryTree::new(new_value)));
                    return;
                }
            }
        }
    }

    pub fn from(new_values: &[T]) -> Self {
        let (first, rest) = new_values.split_first().unwrap();
        let mut root: BinaryTree<T> = BinaryTree::new(*first);

        for value in rest {
            root.insert(*value);
        }
        root
    }
}

#[cfg(test)]
mod tests {
    use crate::BinaryTree;

    #[test]
    fn create_new_btree() {
        let btree = BinaryTree::new(1);
        assert_eq!(btree.value, 1);
    }

    #[test]
    fn insert_left() {
        let btree = BinaryTree::new(1).left(BinaryTree::new(2));
        if let Some(node) = btree.left {
            assert_eq!(node.value, 2);
        }
        assert_eq!(btree.right, None);
    }

    #[test]
    fn insert_right() {
        let btree = BinaryTree::new(1).right(BinaryTree::new(2));
        if let Some(node) = btree.right {
            assert_eq!(node.value, 2);
        }
        assert_eq!(btree.left, None);
    }

    #[test]
    fn insert() {
        let mut btree = BinaryTree::new(1);
        btree.insert(2);
        btree.insert(3);
        btree.insert(47);
        btree.insert(5);

        assert_eq!(
            btree,
            BinaryTree::new(1)
                .left(
                    BinaryTree::new(2)
                        .left(BinaryTree::new(47))
                        .right(BinaryTree::new(5))
                )
                .right(BinaryTree::new(3))
        );

        btree.insert(7);

        assert_eq!(
            btree,
            BinaryTree::new(1)
                .left(
                    BinaryTree::new(2)
                        .left(BinaryTree::new(47))
                        .right(BinaryTree::new(5))
                )
                .right(BinaryTree::new(3).left(BinaryTree::new(7)))
        )
    }

    #[test]
    fn create_btree_from_array() {
        let btree = BinaryTree::from(&[1, 2, 3, 47, 5, 6]);

        assert_eq!(
            btree,
            BinaryTree::new(1)
                .left(
                    BinaryTree::new(2)
                        .left(BinaryTree::new(47))
                        .right(BinaryTree::new(5))
                )
                .right(BinaryTree::new(3).left(BinaryTree::new(6)))
        )
    }
}

// Ref: https://dawchihliou.github.io/articles/binary-tree-insertion-in-rust