second.rs

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

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

pub struct IntoIter<T: Ord>(Link<T>);

impl<T: Ord + Copy> BST<T> {
    pub fn new() -> Self {
        BST { root: None }
    }

    pub fn insert(&mut self, val: T) -> bool {
        self.root.insert(val)
    }

    pub fn search(&self, val: T) -> bool {
        self.root.search(val)
    }
}

impl<T: Ord + Copy> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        let link = self.0.take();
        match link {
            None => None,
            Some(node) => {
                let res = node.value;
                self.0 = node.right;
                Some(res)
            }
        }
    }
}

impl<T: Ord + Copy> IntoIterator for BST<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter(self.root)
    }
}

trait InsertSearch<T: Ord> {
    fn insert(&mut self, entry: T) -> bool;
    fn search(&self, entry: T) -> bool;
}

impl<T: Ord> InsertSearch<T> for Link<T> {
    fn insert(&mut self, val: T) -> bool {
        match *self {
            None  => {
                *self = Some(
                    Box::new(Node::new(val)));
                true
            }
            Some(ref mut node) => {
                if node.value == val {
                    false
                } else if val < node.value {
                    node.left.insert(val)
                } else {
                    node.right.insert(val)
                }
            }
        }
    }

    fn search(&self, val: T) -> bool {
        match *self {
            None => false,
            Some(ref node) => {
                if val == node.value {
                    true
                } else if val < node.value {
                    node.left.search(val)
                } else {
                    node.right.search(val)
                }
            }
        }
    }
}

#[derive(Debug,Clone)]
struct Node<T: Ord> {
    value: T,
    left: Link<T>,
    right: Link<T>
}

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