Career cup 4.7 - CommonAncestorFinder

CommonAncestorFinder.java

package Chapter4;

public class CommonAncestorFinder<T extends Comparable<T>> {
    private BinaryTree<T> tree;

    public CommonAncestorFinder(BinaryTree<T> t) {
	tree = t;
    }

    private boolean containsNode(TreeNode<T> root, TreeNode<T> target) {
	if (root == target)
	    return true;
	if (root == null)
	    return false;
	return containsNode(root.left, target)
		|| containsNode(root.right, target);
    }

    public TreeNode<T> findCommonAnscestor(TreeNode<T> fir, TreeNode<T> sec) {
	// check if nodes contains in the tree
	if (!containsNode(tree.root(), fir) || !containsNode(tree.root(), sec))
	    return null;

	return commonAnscestor(tree.root(), fir, sec);
    }

    private TreeNode<T> commonAnscestor(TreeNode<T> p, TreeNode<T> fir,
	    TreeNode<T> sec) {
	if (p == fir || p == sec)
	    return p;
	boolean isFirInLeft = containsNode(p.left, fir);
	boolean isSecInLeft = containsNode(p.left, sec);

	// both nodes in left sub tree
	if (isFirInLeft && isSecInLeft)
	    return commonAnscestor(p.left, fir, sec);

	// both nodes in left sub tree
	if ((!isFirInLeft) && (!isSecInLeft))
	    return commonAnscestor(p.right, fir, sec);

	// one of them in left and one of them in right
	return p;
    }

    public static void main(String[] args) {
	/*
	 * _______7______ / \ __10__ ___2 / \ / 4 3 _8 \ / 1 11
	 */
	Integer[] pre = { 7, 10, 4, 3, 1, 2, 8, 11 };
	Integer[] in = { 4, 10, 3, 1, 7, 11, 8, 2 };
	BinaryTree<Integer> bt = BinaryTreeBuilder.buildTree(pre, in);
	CommonAncestorFinder<Integer> finder = new CommonAncestorFinder<>(bt);
	TreeNode<Integer> Node_7 = bt.root();
	TreeNode<Integer> Node_4 = bt.root().left.left;
	TreeNode<Integer> Node_1 = bt.root().left.right.right;
	TreeNode<Integer> Node_8 = bt.root().right.left;

	System.out.println("Common ancestor of 7 and 4 is " + finder.findCommonAnscestor(Node_7, Node_4).key);
	System.out.println("Common ancestor of 7 and 8 is " + finder.findCommonAnscestor(Node_7, Node_8).key);
	System.out.println("Common ancestor of 4 and 1 is " + finder.findCommonAnscestor(Node_1, Node_4).key);
	System.out.println("Common ancestor of 4 and 8 is " + finder.findCommonAnscestor(Node_8, Node_4).key);
	System.out.println("Common ancestor of 4 and not existing node is "
			+ finder.findCommonAnscestor(Node_8, new TreeNode<Integer>(13)));
    }
}