Homework 8: Binary Search Trees

A Binary Search Tree is a very commonly used data structure, about which you will learn much more in 146, that stores numbers in a tree where every node has two children (thus, binary). Each node contains a number. All the numbers on the left branch of a node are smaller than that node and, similarly, all the numbers on the right branch of a node are bigger than the node. The figure on the right shows an example.
Below you will find a partial implementation of a binary search tree with three methods missing: add, max, and height. For this homework you will implement these methods.

public class BinarySearchTree {

 private BinarySearchTree left;
 
 private BinarySearchTree right;
 
 private int data;
 
 public BinarySearchTree() {
  left = null;
  right = null;
 }
 
 /** Create a tree that consists of just one node with no children. */
 public BinarySearchTree(int data) {
  left = null;
  right = null;
  this.data = data;
 }
 
 /** Adds new number n to this BinarySearchTree, placing it in its correct place.
  * 
  * @param n the number to be added
  */
 public void add (int n) {
           //TODO
 }
 
 /** Returns the maximum number in this tree. */
 public int max() {
           //TODO
 }
 
 /** Returns the height of this tree. */
 public int height() {
           //TODO
 }
 
 public String toString() {
  return toString("");
 }
 
 public String toString(String prefix) {
  String result = "";
  if (right != null)
   result += right.toString(prefix + "-");
  else
   result += prefix + "- *\n"; 
  
  result += prefix + " " + data + "\n";
  
  if (left != null)
   result += left.toString(prefix + "-");
  else
   result += prefix + "- *\n";
    
  return result;  
 }
 
 
 public static void main(String[] args) {
  BinarySearchTree tree = new BinarySearchTree(8);
  tree.add(3);
  tree.add(10);
  tree.add(1);
  tree.add(6);
  tree.add(14);
  tree.add(4);
  tree.add(7);
  tree.add(13);
  System.out.println(tree);
  System.out.println("Max=" + tree.max());
  System.out.println("Height=" + tree.height());

 }
}

The main method shown above constructs the tree shown in the figure. After you properly implement the methods, that main will run and will print out:

--- *
-- 14
---- *
--- 13
---- *
- 10
-- *
 8
---- *
--- 7
---- *
-- 6
---- *
--- 4
---- *
- 3
--- *
-- 1
--- *

Max=14
Height=4

This homework is due Tuesday, November 17 at noon.