/****************************************************************************/
/*                                                                          */
/*                  Calculating the Depth of a Binary Tree                  */
/*                                                                          */
/*                       December 1997, Toshimi Minoura                     */
/*                       November 1999, Jacob Lundberg                      */
/*                                                                          */
/****************************************************************************/

// The Depth of nodes in a Binary Tree is computed.

class Operator {                       // class for operators
  public char symbol;                  // +, *, etc.

  Operator(char x) { symbol = x; }     // constructor for an Operator object

  public int eval(int x, int y) {      // apply this operator to two integers
    if (symbol == '+') {               // this operator is addition
      return x + y;
    }
    if (symbol == '*') {               // this operator is multiplication
      return x * y;
    }
    return -1;                         // illegal operator encountered
  }
  public String toString() {
    return "" + symbol;                // convert char to String and return it
  }
}

class Node {
  String name;                         // name of this node, for debugging
  public Operator operator;            // operator represented by this node
  public int value;                    // value associated with this node
  Node leftChild;                      // left subexpression
  Node rightChild;                     // right subexpression

  Node(String name, int val) {         // constructor for a leaf node
    this.name = name;                  // set name
    operator = null; 
    value = val;                       // set value for this leaf node
    leftChild = null;                  // no left subexpression
    rightChild = null;                 // no right subexpression
  }

  Node(String name, char opCode, Node leftNode, Node rightNode) {
    this.name = name;                  // set name
    operator = new Operator(opCode);   // create operator for given symbol
    value = -1;                        // no initial value
    if( leftNode != null )
      leftChild = leftNode;            // set left subexpression
    if( rightNode != null )
      rightChild = rightNode;          // set right subexpression
  }

  // Calculate depth in a subtree.  Call on root for whole tree.
  public void depth() {
    System.out.println( "Starting printing depths." );
    System.out.println( "Depth of subexpression root " + this.name + ": 0." );
    if( leftChild != null )
      leftChild.depth( 0 );
    if( rightChild != null )
      rightChild.depth( 0 );
    System.out.println( "Finished printing depths." );
  }

  // Levels > 0 calculated here.
  private void depth( int level ) {
    System.out.println( "Depth of subexpression node " + this.name + ": " + ++level + "." );
    if( leftChild != null )
      leftChild.depth( level );
    if( rightChild != null )
      rightChild.depth( level );
  }

  public int eval() {          // evaluate subexpression below this node
    if (operator == null) {    // is this a leaf node?
      return value;            // yes, return value stored in this node
    } else {                   // non-leaf, calculate value for subexpression
      value = operator.eval(leftChild.eval(), rightChild.eval());
      System.out.println("Subexpression evaluated for " + name + ": " + value);
      return value;
    }
  }

  public String toString() {     // convert an expression tree to String
    if (operator == null) {      // leaf node?
      return "" + value;         // yes, convert int to String and return
    } else {                     // return String for subexpression
      return "(" + leftChild + operator + rightChild + ")";
    }
  } 
}
 
class DepthTree {                             // class for Java application
  public static void main(String argv[]) {      // application main function
    Node node2 = new Node("n2", 1);             // leaf node with value 1
    Node node4 = new Node("n4", 2);             // leaf node with value 2
    Node node7 = new Node("n7", 3);             // leaf node with value 3
    Node node8 = new Node("n8", 4);             // leaf node with value 4
    Node node9 = new Node("n9", 5);             // leaf node with value 5
    Node node3 = new Node("n3", '+', node4,  null);  // non-leaf
    Node node1 = new Node("n1", '+', node2, node3);  // non-leaf
    Node node6 = new Node("n6", '+', node7, node8);  // non-leaf
    Node node5 = new Node("n5", '+', node6, node9);  // non-leaf
    Node node0 = new Node("n0", '+', node1, node5);  // non-leaf
    System.out.println("Depth of expression " + node0 + ".");
    node0.depth();
    System.out.println("Evaluation completed.");
  }
}