use std::cmp::Ordering;

enum BinaryTree<T> {
    Empty,
    NonEmpty(Box<TreeNode<T>>),
}

struct TreeNode<T> {
    element: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>,
}

impl<T: Ord> BinaryTree<T> {
    fn add(&mut self, value: T) {
        match *self {
            BinaryTree::Empty => *self = BinaryTree::NonEmpty(Box::new(TreeNode { element: value, left: BinaryTree::Empty, right: BinaryTree::Empty})),
            BinaryTree::NonEmpty(ref mut node) =>
                if value <= node.element {
                    node.left.add(value);
                } else {
                    node.right.add(value);
                }
        }
    }

    fn search(&self, value: T) -> Option<T> {
        match self {
            BinaryTree::Empty => None,
            BinaryTree::NonEmpty(node) => match node.element.cmp(&value) {
                Ordering::Equal => Some(value),
                Ordering::Less => node.right.search(value),
                Ordering::Greater => node.left.search(value),
            }
        }
    }
}

fn main() {
    let mut tree = BinaryTree::Empty;
    tree.add(5);
    tree.add(6);
    tree.add(1);
    tree.add(4);
    tree.add(9);

    let result = tree.search(5);
    println!("res {:?}", result);

    println!("\nnext example");
    let result = tree.search(4);
    println!("res: {:?}", result);

    println!("\nnext example");
    let result = tree.search(9);
    println!("res: {:?}", result);

    println!("\nnext example");
    let result = tree.search(10);
    println!("res: {:?}", result);
}