Using RUST, implement a [binary search tree](https://en.wikipedia.org/wiki/Binar

Question

 Using RUST, 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).  ## Public API  Your program must provide 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!()     } } 

Explanation / Answer

#[derive(Debug)] pub struct Tree(Option); #[derive(Debug)] pub struct Node { elem: T, left: Tree, right: Tree, } // MUTABLE BORROW STRUCT pub struct IterMut { next: &'a mut Tree, } // MUTABLE BORROW NEXT (I'M STUCK HERE, NOTHING WORKS) impl { type Item = &'a mut T; fn next(&mut self) -> Option { // 1 try: cannot infer lifetime self.next.0.as_mut().map(|node| { self.next = &mut node.right; &mut node.elem }) // 2 try: node.right, node.elem does not live long enough self.next.0.take().map(|node| { self.next = &mut node.right; &mut node.elem }) } }

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.