/*
           +------+              
           | IBST |<------------+
           +------+             |
           +------+             |
              |                 |
             / \                |
             ---                |
              |                 |
     ----------------           |
     |              |           |
  +------+    +------------+    |
  | Leaf |    | Node       |    |
  +------+    +------------+    |
  +------+    | int value  |    |
              | IBST left  |-+  |
              | IBST right |-+  |
              +------------+ |  |
                             |  |
                             +--+

*/

// represent binary search trees
interface IBST {
 // insert given value into this binary search tree.
 IBST insert(int value);

 // compute height of this binary search tree.
 int height();
}

// represent leaves
class Leaf implements IBST {
  Leaf() {}
  // insert given value into this leaf.
  IBST insert(int value) {
    return new Node(value, this, this);
  }
  
  // compute the height of this leaf.
  int height() {
     return 0;
  }
}

// to represent nodes
class Node implements IBST {
  int value;
  IBST left;
  IBST right;

  Node(int value, IBST left, IBST right) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
  
  // insert given value into this node.
  IBST insert(int value) {
    if (this.value > value) {
      return new Node(this.value, this.left.insert(value), this.right); }
    else {
      return new Node(this.value, this.left, this.right.insert(value));
    }
  }
     
  // compute height of this node.
  int height() {
  /* template
     this.value ... int
     this.left  ... IBST
     this.right ... IBST
     this.insert(int) ... IBST
     this.left.height() ... int
     this.right.height() ... int
  */

    return max(this.left.height(), this.right.height()) + 1;
  }
  
  // compute the maximum of two given numbers.
  int max(int x, int y) {
    if (x > y) return x; else return y;
  }
}

class IBSTExamples {
  IBSTExamples () {}
  IBST leaf = new Leaf();
  
  IBST tree = new Node(8, new Node(7, new Node(3, leaf, leaf), leaf),
                          new Node(10, new Node(9, leaf, leaf), leaf));
                          
  boolean insertTests =
    ((check leaf.insert(5) expect new Node(5, leaf, leaf)) &&
     (check leaf.insert(5).insert(3) expect new Node(5, new Node(3, leaf, leaf), leaf)));
    
  Node n = new Node(0, leaf, leaf);
  boolean maxTests =
    ((check n.max(10,20) expect 20) &&
     (check n.max(20,10) expect 20));
}