cc150_4_7.java

package cc150_4_7;


public class CommonAncestor<Key extends Comparable<Key>> {
	
	private Node root;
	class Node{
		private Key key;
		public Node left;
		public Node right;
		
		public Node(Key data){
			this.key = data;
		}
	}
	
	public CommonAncestor(Key[] keys){
			for(Key key:keys){
				put(key);
			}
	}
	
	public void put(Key key){
		root = put(root,key);
	}
	
	public Node put(Node x, Key key){
		if(x == null) 
		{
			Node temp = new Node(key);
			return temp;
		}
		int cmp = key.compareTo(x.key);
		if(cmp < 0) {
			x.left = put(x.left,key);
			
		}
		else if(cmp > 0) {
			x.right = put(x.right,key);
			
		}
		return x;
	}
	
	public void printTree(Node head){
		if(head == null) return;
		printTree(head.left);
		System.out.print(head.key + ", ");
		printTree(head.right);
		
	}
	
	
	public Node Ancestor(Node root, Node p, Node q){
		if(root == null) return null;
		if(root == p || root == q) return root;
		
		boolean p_on_left = tranverse(root.left,p);
		boolean q_on_left = tranverse(root.left,q);
		
		// If p,q on different sides, return root
		if(p_on_left != q_on_left) return root;
		
		// If p,q on the same side, return ancestor(root.left/root.right,p,q)
		// If on left
		if(p_on_left && q_on_left) return Ancestor(root.left,p,q);
		// If on right
		else if(!p_on_left && !q_on_left) return Ancestor(root.right,p,q);
		else
			return null;
		
	}
	
	
	
	private boolean tranverse(Node left, Node p) {
		// TODO Auto-generated method stub
		if(left == null) return false;
		if(left == p) return true;
		return tranverse(left.left,p) || tranverse(left.right,p);
		
	}

	public static void main(String[] args) {
		/*	_______7______
	       /              \
	    __4__          __10
	   /     \        /     \
	  3              8       11
	 /             
	1           		
	 \
	  2
	
	
	*/
	Integer[] data = { 7, 10, 4, 3, 1, 2, 8, 11 };
	CommonAncestor<Integer> test = new CommonAncestor<Integer>(data);
	test.printTree(test.root);
	System.out.println("");
	
	System.out.println(test.root.left.left.key);
	System.out.println(test.root.right.key);
	System.out.println("Root is :" + test.root.left.key);
	
	System.out.println(test.Ancestor(test.root, test.root.right.right, test.root.right.left).key);
	}
	
}