use std::cmp::Ordering;

type NodePtr<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
pub struct Node<T>
where
    T: Ord,
{
    key: T,
    left: NodePtr<T>,
    right: NodePtr<T>,
}

#[derive(Debug)]
pub struct BST<T>
where
    T: Ord,
{
    root: NodePtr<T>,
}

impl<T> BST<T>
where
    T: Ord,
{
    pub fn new() -> BST<T> {
        BST { root: None }
    }

    pub fn find(&self, v: &T) -> &NodePtr<T> {
        let mut cur = &self.root;

        while let Some(node) = cur {
            match node.key.cmp(v) {
                Ordering::Equal => return cur,
                Ordering::Less => cur = &node.right,
                Ordering::Greater => cur = &node.left,
            };
        }

        &None
    }

    pub fn insert(&mut self, val: T) {
        if let Some(_) = self.find(&val) {
            return;
        }

        let mut cur = &mut self.root;
        while let Some(node) = cur {
            match node.key.cmp(&val) {
                Ordering::Less | Ordering::Equal => cur = &mut node.right,
                Ordering::Greater => cur = &mut node.left,
            };
        }

        cur.replace(Box::from(Node {
            key: val,
            left: None,
            right: None,
        }));
    }
}

fn main() {
    let mut bst: BST<i32> = BST::new();
    bst.insert(8);
    bst.insert(3);
    bst.insert(10);
    bst.insert(5);
    bst.insert(5);

    println!("{:?}", bst.find(&5));
    println!("{:?}", bst.find(&10));
    println!("{:?}", bst.find(&7));
}