use std::cmp::max;

enum Tree<T>{
    Empty,
    Node(T, Box<Tree<T>>, Box<Tree<T>>)
}

impl<T> Tree<T>
    where T: PartialOrd
{
    fn depth(&self) -> usize {
        match *self {
            Tree::Empty => 0,
            Tree::Node(_, ref left, ref right) =>
                1 + max(left.depth(), right.depth())
        }
    }

    fn insert(self, value: T) -> Self {
        match self {
            Tree::Empty => {
                Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty))
            },
            Tree::Node(old_value, left, right) => {
                if value < old_value {
                    Tree::Node(old_value, Box::new(left.insert(value)), right)
                } else {
                    Tree::Node(old_value, left, Box::new(right.insert(value)))
                }
            },
        }
    }

    fn insert_mut(&mut self, value: T) -> &mut Self {
        match *self {
            Tree::Empty => {
                *self = Tree::Node(value, Box::new(Tree::Empty), Box::new(Tree::Empty));
            },
            Tree::Node(ref old_value, ref mut left, ref mut right) => {
                if &value < old_value {
                    left.insert_mut(value);
                } else {
                    right.insert_mut(value);
                }
            }
        }

        self
    }
}

fn main() {
    let tree = Tree::Empty
        .insert(5)
        .insert(4)
        .insert(3)
        .insert(6)
        .insert(2);

    println!("Depth is: {}", tree.depth());

    let mut tree = Tree::Empty;
    tree
        .insert_mut(5)
        .insert_mut(4)
        .insert_mut(3)
        .insert_mut(6)
        .insert_mut(2);

    println!("Depth is: {}", tree.depth());
}