public class BST {
  int value; 
  BST left, right; 
  public BST(int v, BST l, BST r) {
   this.value = v; 
   this.left = l;
   this.right = r; 
  }
  public String toString() {
    return this.left + " " + this.value + " " + this.right;  
  }
  public boolean insert(int v) {
    if (this.value == v) { 
      return false;  
    } else {
      if (v < this.value) { 
        if (this.left == null) {
          this.left = new BST(v, null, null);
          return true; 
        } else {
          return this.left.insert(v); 
        }
      } else {
        if (this.right == null) {
          this.right = new BST(v, null, null);
          return true; 
        } else {
          return this.right.insert(v); 
        } 
      }
    }
  }
  public static void main(String[] args) {
    BST a = new BST(8, null, null); 
    System.out.println( a ); 
    a.insert(3);
    System.out.println( a ); 
    a.insert(1);
    System.out.println( a ); 
    a.insert(4); 
    System.out.println( a ); 
  }
  
  
}
--

public class BST {
  int value; 
  BST left, right; 
  public BST(int v, BST l, BST r) {
   this.value = v; 
   this.left = l;
   this.right = r; 
  }
  public String toString() {
    return this.left + " " + this.value + " " + this.right;  
  }
  public static int height(BST node) {
    if (node == null) return 0; 
    else return node.depth(); 
  }
  public int depth() {
    return 1 + Math.max( BST.height(this.left), BST.height(this.right) );   
  }
  public int find(int k) { // k is 1 based find(3) produces element index 2 
    System.out.println("Looking at: " + this.value + " seeking " + k); 
    if (k == 1 + BST.height(this.left)) return this.value; 
    else if ( k <= BST.height(this.left)) {
      return this.left.find(k); 
    } else {
      return this.right.find( k - 1 - BST.height(this.left)); 
    }
  }
  public boolean insert(int v) {
    if (this.value == v) { 
      return false;  
    } else {
      if (v < this.value) { 
        if (this.left == null) {
          this.left = new BST(v, null, null);
          return true; 
        } else {
          return this.left.insert(v); 
        }
      } else {
        if (this.right == null) {
          this.right = new BST(v, null, null);
          return true; 
        } else {
          return this.right.insert(v); 
        } 
      }
    }
  }
  public static void main(String[] args) {
    BST a = new BST(8, null, null); 
    System.out.println( a ); 
    a.insert(3);
    System.out.println( a ); 
    a.insert(1);
    System.out.println( a ); 
    a.insert(6); 
    System.out.println( a ); 
    a.insert(4); 
    System.out.println( a ); 
    a.insert(7); 
    System.out.println( a ); 
    a.insert(10); 
    System.out.println( a ); 
    a.insert(14); 
    System.out.println( a ); 
    a.insert(13); 
    System.out.println( a ); 
    System.out.println( a.depth() ); 
    System.out.println( a );     
    System.out.println( a.find(6) ); 
  }  
}

--

public class BST {
  int value; 
  BST left, right; 
  public BST(int v, BST l, BST r) {
   this.value = v; 
   this.left = l;
   this.right = r; 
  }
  public String toString() {
    return this.left + " " + this.value + " " + this.right;  
  }
  public static int size(BST node) {
    if (node == null) return 0; 
    else return 1 + BST.size(node.left) + BST.size(node.right); 
  }
  public int find(int k) { // k is 1 based find(3) produces element index 2 
    // System.out.println("Looking at: " + this.value + " seeking " + k); 
    if (k == 1 + BST.size(this.left)) return this.value; 
    else if ( k <= BST.size(this.left)) {
      return this.left.find(k); 
    } else {
      return this.right.find( k - 1 - BST.size(this.left)); 
    }
  }
  public boolean insert(int v) {
    if (this.value == v) { 
      return false;  
    } else {
      if (v < this.value) { 
        if (this.left == null) {
          this.left = new BST(v, null, null);
          return true; 
        } else {
          return this.left.insert(v); 
        }
      } else {
        if (this.right == null) {
          this.right = new BST(v, null, null);
          return true; 
        } else {
          return this.right.insert(v); 
        } 
      }
    }
  }
  public static void main(String[] args) {
    BST a = new BST(8, null, null); 
    System.out.println( a ); 
    a.insert(3);
    System.out.println( a ); 
    a.insert(1);
    System.out.println( a ); 
    a.insert(6); 
    System.out.println( a ); 
    a.insert(4); 
    System.out.println( a ); 
    a.insert(7); 
    System.out.println( a ); 
    a.insert(10); 
    System.out.println( a ); 
    a.insert(14); 
    System.out.println( a ); 
    a.insert(13); 
    System.out.println( a ); 
    System.out.println( BST.size(a) ); 
    System.out.println( a );     
    System.out.println( "1: " + a.find(1) ); 
    System.out.println( "2: " + a.find(2) ); 
    System.out.println( "3: " + a.find(3) ); 
    System.out.println( "4: " + a.find(4) ); 
    System.out.println( "5: " + a.find(5) ); 
    System.out.println( "6: " + a.find(6) ); 
    System.out.println( "7: " + a.find(7) ); 
    System.out.println( "8: " + a.find(8) ); 
    System.out.println( "9: " + a.find(9) ); 
    
  }  
}

--

0. Error cases
1. Code from the book
2. Why slow, how can you speed it up?
3. Can we print to see the structure of the tree 

start with empty BST a and insert 1 2 3 4 5 6 7 8 9 in this order 

start with empty BST a and insert 9 8 7 6 5 4 3 2 1 in this order 

start with empty BST a and insert 4 1 6 3 2 8 9 7 5 in this order 

         1
          \ 
           2
            \ 
             3 
              \ 
               4
                \
                 5 
                  \ 
                   6
                    \ 
                     7 
                      \     
                       8 
                        \ 
                         9


                 9
                /
               8
              /
             7
            /
           6
          /
         5
        /
       4
      /
     3
    /
   2
  /
 1

start with empty BST a and insert 4 1 6 3 2 8 9 7 5 in this order 

                              4
                            /   \ 
                           1     6
                            \   / \ 
                             3 5   8
                            /     / \ 
                           2     7   9




http://silo.cs.indiana.edu:8346/c212/milestones/ch17/section_3/BinarySearchTree.java

public class BST {
  int value; 
  BST left, right; 
  public BST(int v, BST l, BST r) {
   this.value = v; 
   this.left = l;
   this.right = r; 
  }
  public String print() {
    return "(" + this.value + " " + 
                 ((this.left == null) ? "." : this.left.print()) + " " + 
                 ((this.right == null) ? "." : this.right.print())  + ")";  
  }
  public String toString() {
    return this.left + " " + this.value + " " + this.right;  
  }
  public static int size(BST node) {
    if (node == null) return 0; 
    else return 1 + BST.size(node.left) + BST.size(node.right); 
  }
  public int find(int k) { // k is 1 based find(3) produces element index 2 
    // System.out.println("Looking at: " + this.value + " seeking " + k); 
    if (k == 1 + BST.size(this.left)) return this.value; 
    else if ( k <= BST.size(this.left)) {
      return this.left.find(k); 
    } else {
      return this.right.find( k - 1 - BST.size(this.left)); 
    }
  }
  public boolean insert(int v) {
    if (this.value == v) { 
      return false;  
    } else {
      if (v < this.value) { 
        if (this.left == null) {
          this.left = new BST(v, null, null);
          return true; 
        } else {
          return this.left.insert(v); 
        }
      } else {
        if (this.right == null) {
          this.right = new BST(v, null, null);
          return true; 
        } else {
          return this.right.insert(v); 
        } 
      }
    }
  }
  public static void main(String[] args) {
    BST a = new BST(8, null, null); 
    System.out.println( a ); 
    a.insert(3);
    System.out.println( a ); 
    a.insert(1);
    System.out.println( a ); 
    a.insert(6); 
    System.out.println( a ); 
    a.insert(4); 
    System.out.println( a ); 
    a.insert(7); 
    System.out.println( a ); 
    a.insert(10); 
    System.out.println( a ); 
    a.insert(14); 
    System.out.println( a ); 
    a.insert(13); 
    System.out.println( a ); 
    System.out.println( BST.size(a) ); 
    System.out.println( a );     
    System.out.println( "1: " + a.find(1) ); 
    System.out.println( "2: " + a.find(2) ); 
    System.out.println( "3: " + a.find(3) ); 
    System.out.println( "4: " + a.find(4) ); 
    System.out.println( "5: " + a.find(5) ); 
    System.out.println( "6: " + a.find(6) ); 
    System.out.println( "7: " + a.find(7) ); 
    System.out.println( "8: " + a.find(8) ); 
    System.out.println( "9: " + a.find(9) ); 
    
    System.out.println( a.print() ); 
    
  }  
}

--