Using ONLY RUST not C C Java or anything else implement a bi

 Using ONLY RUST, not C, C++, Java or anything else, implement a [binary search tree](https://en.wikipedia.org/wiki/Binary_search_tree) that supports insert, search, and [traversal](https://en.wikipedia.org/wiki/Tree_traversal). Please have it fully functional.  The program must use the following public API.  ``` pub struct Tree<T> {     ... }  impl<T: Ord> Tree<T> {     /// Creates an empty tree     pub fn new() -> Self {         unimplemented!()     }      /// Returns `false` if `key` already exists in the tree, and `true` otherwise.     pub fn insert(&mut self, key: T) -> bool {         unimplemented!()     }      /// Returns `true` if `key` exists in the tree, and `false` otherwise.     pub fn find(&self, key: &T) -> bool {         unimplemented!()     }      /// Returns the preorder traversal of the tree.     pub fn preorder(&self) -> Vec<&T> {         unimplemented!()     }      /// Returns the inorder traversal of the tree.     pub fn inorder(&self) -> Vec<&T> {         unimplemented!()     }      /// Returns the postorder traversal of the tree.     pub fn postorder(&self) -> Vec<&T> {         unimplemented!()     } } 

Solution

Executable Code

#![feature(box_syntax, box_patterns)]

use std::collections::VecDeque;

#[derive(Debug)]
struct MyTreeNode<T>
{
    myvalue: T,
    myleft: Option<Box<MyTreeNode<T>>>,
    myright: Option<Box<MyTreeNode<T>>>,
}

enum MyTraversalMethod
{
    MyPreOrder,
    MyInOrder,
    MyPostOrder,
}

impl<T> MyTreeNode<T>
{
    pub fn new(myarr: &[[i8; 3]]) -> MyTreeNode<i8>
    {

        let myl = match myarr[0][1]
        {
            -1 => None,
            i @ _ => Some(Box::new(MyTreeNode::<i8>::new(&myarr[(i - myarr[0][0]) as usize..]))),
        };
        let myr = match myarr[0][2]
        {
            -1 => None,
            i @ _ => Some(Box::new(MyTreeNode::<i8>::new(&myarr[(i - myarr[0][0]) as usize..]))),
        };
        MyTreeNode
        {
            myvalue: myarr[0][0],
            myleft: myl,
            myright: myr,
        }
    }

    pub fn mytraverse(&self, mytr: &MyTraversalMethod) -> Vec<&MyTreeNode<T>>
    {
        match mytr
        {
            &MyTraversalMethod::MyPreOrder => self.iterativepreorder(),
            &MyTraversalMethod::MyInOrder => self.iterativeinorder(),
            &MyTraversalMethod::MyPostOrder => self.iterativepostorder(),           
        }
    }

    fn iterativepreorder(&self) -> Vec<&MyTreeNode<T>>
    {
        let mut stack: Vec<&MyTreeNode<T>> = Vec::new();
        let mut myres: Vec<&MyTreeNode<T>> = Vec::new();

        stack.push(self);
        while !stack.is_empty()
        {
            let mynode = stack.pop().unwrap();
            myres.push(mynode);
            match mynode.myright
            {
                None => {}
                Some(box ref myn) => stack.push(myn),
            }
            match mynode.myleft
            {
                None => {}
                Some(box ref myn) => stack.push(myn),
            }
        }
        myres
    }
    fn iterativeinorder(&self) -> Vec<&MyTreeNode<T>>
    {
        let mut stack: Vec<&MyTreeNode<T>> = Vec::new();
        let mut myres: Vec<&MyTreeNode<T>> = Vec::new();
        let mut myp = self;
        loop
        {
          
            loop
            {
                match myp.myright
                {
                    None => {}
                    Some(box ref myn) => stack.push(myn),
                }
                stack.push(myp);
                match myp.myleft
                {
                    None => break,
                    Some(box ref myn) => myp = myn,
                }
            }
            myp = stack.pop().unwrap();
            while !stack.is_empty() && myp.myright.is_none()
            {
                myres.push(myp);
                myp = stack.pop().unwrap();
            }
            myres.push(myp);
            if stack.is_empty()
            {
                break;
            }
            else
            {
                myp = stack.pop().unwrap();
            }
        }
        myres
    }

    fn iterativepostorder(&self) -> Vec<&MyTreeNode<T>>
    {
        let mut stack: Vec<&MyTreeNode<T>> = Vec::new();
        let mut myres: Vec<&MyTreeNode<T>> = Vec::new();

        stack.push(self);
        while !stack.is_empty()
        {
            let mynode = stack.pop().unwrap();
            myres.push(mynode);
            match mynode.myleft
            {
                None => {}
                Some(box ref myn) => stack.push(myn),
            }
            match mynode.myright
            {
                None => {}
                Some(box ref myn) => stack.push(myn),
            }
        }
        let reviter = myres.iter().rev();
        let mut rev: Vec<&MyTreeNode<T>> = Vec::new();
        for elements in reviter
        {
            rev.push(elements);
        }
        rev
    }
}

fn main()
{

    let arrtree = [[1, 2, 3],
                    [2, 4, 5],
                    [3, 6, -1],
                    [4, 7, -1],
                    [5, -1, -1],
                    [6, 8, 9],
                    [7, -1, -1],
                    [8, -1, -1],
                    [9, -1, -1]];

    let myroot = MyTreeNode::<i8>::new(&arrtree);

    for methodlabel in [(MyTraversalMethod::MyPreOrder, \"pre-order:\"),
                         (MyTraversalMethod::MyInOrder, \"in-order:\"),
                         (MyTraversalMethod::MyPostOrder, \"post-order:\")]
                            .iter()
    {
        print!(\"{}\\t\", methodlabel.1);
        for myn in myroot.mytraverse(&methodlabel.0)
        {
            print!(\" {}\", myn.myvalue);
        }
        print!(\"\ \");
    }
}