/*
 * TreePost.java
 *
 */

import net.datastructures.*;

public class TreeAncestor {
    
    static int order;
    
    public static void TreePost(LinkedBinaryTree t, Position p) {
        if (t.hasLeft(p)) {
            TreePost(t, t.left(p));
        }

        if (t.hasRight(p)) {
            TreePost(t, t.right(p));
        }

        MyData1 data = (MyData1)p.element();
        System.out.println("The Postorder of "+data.A+ " is "+ order);
        data.B = order;
        order++;
    }
    
    public static boolean isAncester(LinkedBinaryTree t, Position u, Position v) {
        Position x;
        x = t.parent(v); 
        while (x != u && t.root()!=x) {
            x = t.parent(x);
        }
        if (x==u)
            return true;
        else
            return false;
    }
    public static void main(String[] args) {
        
        LinkedBinaryTree  t = new LinkedBinaryTree();
        Position parent;       
 
        /* 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);
        
        /* Postorder tranversal of tree t */
        order = 1;
        //TreePost (t, t.root());
        System.out.print("The result of isAncester(t, B, I) is ");
        boolean result1 = isAncester(t, t.left(t.root()), t.right(t.right(t.left(t.root()))));
        System.out.println(result1);
        
        System.out.print("The result of isAncester(t, B, C) is ");
        boolean result2 = isAncester(t, t.left(t.root()), t.right(t.root()));
        System.out.println(result2);
    }
}