/*
 * TreeHeight2.java
 *
 * 
 */

import net.datastructures.*;
import java.util.Iterator;

public class TreeHeight2 {
    
    // get the height of node v
    public static int height2 (Tree t, Position v) {
        if ( t.isExternal(v) )  return 0;
        int h = 0;
        Iterator c = t.children(v);
        while (c.hasNext()) {
            h = Math.max(h, height2(t, (Position)c.next()) );
        }
        return 1 + h;
    }
    
    public static void main(String[] args) {
        
        LinkedBinaryTree  t = new LinkedBinaryTree();
        Position parent, B;
        int h;
 
        /* generate a tree t, insert 9 nodes */ 
        t.addRoot(new MyData1('A'));
        
        parent = t.root();
        t.insertLeft(parent, new MyData1('B'));
        t.insertRight(parent, new MyData1('C'));
        
        parent = t.left(t.root());
        t.insertLeft(parent, new MyData1('D'));
        t.insertRight(parent, new MyData1('E'));
        
        parent = t.right(t.root());
        t.insertLeft(parent, new MyData1('F'));
        t.insertRight(parent, new MyData1('G'));
        
        parent = t.right(t.left(t.root()));
        t.insertLeft(parent, new MyData1('H'));
        t.insertRight(parent, new MyData1('I'));
        
        /* print the structure of tree t */
        MyData1.printTree(t);
        
        /* get the height of B */
        B = t.left(t.root());
        h = height2 (t, B);
        System.out.println("The height of B is " + h);
    }
}