## Binary search trees Implement a [binary search tree](https://en.wikipedia.org

Question

 ## Binary search trees  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

import java.util.*; public class BST implements Iterable { public static void main(String[] args) { Integer[] a = {1,5,2,7,4}; BST bst = new BST(); for(Integer n : a) bst.insert(n); bst.preOrderTraversal(); System.out.println(); bst = new BST(new MyComp1()); for(Integer n : a) bst.insert(n); bst.preOrderTraversal(); System.out.println(); bst.inOrderTraversal(); System.out.println(); for(Integer n : bst) System.out.print(n); System.out.println(); System.out.println(bst); bst.restore(new Integer[] {11,8,6,4,7,10,19,43,31,29,37,49}, new Integer[] {4,6,7,8,10,11,19,29,31,37,43,49}); bst.preOrderTraversal(); System.out.println(); bst.inOrderTraversal(); System.out.println(); System.out.println("diameter = " + bst.diameter()); System.out.println("width = " + bst.width()); } private Node root; private Comparator comparator; public BST() { root = null; comparator = null; } public BST(Comparator comp) { root = null; comparator = comp; } private int compare(T x, T y) { if(comparator == null) return x.compareTo(y); else return comparator.compare(x,y); } public void insert(T data) { root = insert(root, data); } private Node insert(Node p, T toInsert) { if (p == null) return new Node(toInsert); if (compare(toInsert, p.data) == 0) return p; if (compare(toInsert, p.data) < 0) p.left = insert(p.left, toInsert); else p.right = insert(p.right, toInsert); return p; } public boolean search(T toSearch) { return search(root, toSearch); } private boolean search(Node p, T toSearch) { if (p == null) return false; else if (compare(toSearch, p.data) == 0) return true; else if (compare(toSearch, p.data) < 0) return search(p.left, toSearch); else return search(p.right, toSearch); } public void delete(T toDelete) { root = delete(root, toDelete); } private Node delete(Node p, T toDelete) { if (p == null) throw new RuntimeException("cannot delete."); else if (compare(toDelete, p.data) < 0) p.left = delete (p.left, toDelete); else if (compare(toDelete, p.data) > 0) p.right = delete (p.right, toDelete); else { if (p.left == null) return p.right; else if (p.right == null) return p.left; else { p.data = retrieveData(p.left); p.left = delete(p.left, p.data) ; } } return p; } private T retrieveData(Node p) { while (p.right != null) p = p.right; return p.data; } public String toString() { StringBuffer sb = new StringBuffer(); for(T data : this) sb.append(data.toString()); return sb.toString(); } public void preOrderTraversal() { preOrderHelper(root); } private void preOrderHelper(Node r) { if (r != null) { System.out.print(r+" "); preOrderHelper(r.left); preOrderHelper(r.right); } } public void inOrderTraversal() { inOrderHelper(root); } private void inOrderHelper(Node r) { if (r != null) { inOrderHelper(r.left); System.out.print(r+" "); inOrderHelper(r.right); } } public BST clone() { BST twin = null; if(comparator == null) twin = new BST(); else twin = new BST(comparator); twin.root = cloneHelper(root); return twin; } private Node cloneHelper(Node p) { if(p == null) return null; else return new Node(p.data, cloneHelper(p.left), cloneHelper(p.right)); } public int height() { return height(root); } private int height(Node p) { if(p == null) return -1; else return 1 + Math.max( height(p.left), height(p.right)); } public int countLeaves() { return countLeaves(root); } private int countLeaves(Node p) { if(p == null) return 0; else if(p.left == null && p.right == null) return 1; else return countLeaves(p.left) + countLeaves(p.right); } public void restore(T[] pre, T[] in) { root = restore(pre, 0, pre.length-1, in, 0, in.length-1); } private Node restore(T[] pre, int preL, int preR, T[] in, int inL, int inR) { if(preL

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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