Q4_7.java

public class Q4_7 {
	public static void main(String[] args) {
		int[] test = { 1, 2, 3, 4, 5, 6, 7, 8 };
		TreeNode<Integer> rootNode = new Q4_3().arrayToBST(test, 0, 7);
		TreeNode<Integer> cur = rootNode;
		System.out.println(covers(rootNode, rootNode.right.left));
		System.out.println(covers(rootNode, rootNode.right.right.right));

		System.out.println(findCommonAncestor(rootNode, rootNode.left.left,
				rootNode.right).value); // 4
		System.out.println(findCommonAncestor(rootNode, rootNode,
				rootNode.right.right).value); // 4
		System.out.println(findCommonAncestor(rootNode, rootNode.right,
				rootNode.right.right).value); // 6
		System.out.println(findCommonAncestor(rootNode, rootNode.right.left,
				rootNode.right.right.right).value); // 6
		System.out.println(findCommonAncestor(rootNode, rootNode.left,
				new TreeNode(10)) == null);
	}

	static TreeNode<Integer> findCommonAncestor(TreeNode<Integer> root,
			TreeNode<Integer> node1, TreeNode<Integer> node2) {
		if (root == null || !covers(root, node1) || !covers(root, node2))
			return null;
		else
			return findCommonAncestorHelper(root, node1, node2);
	}

	static boolean covers(TreeNode<Integer> root, TreeNode<Integer> node) {
		if (root == null)
			return false;
		if (root == node)
			return true;
		// System.out.println(root.value);
		return covers(root.left, node) || covers(root.right, node);
	}

	static TreeNode<Integer> findCommonAncestorHelper(TreeNode<Integer> root,
			TreeNode<Integer> node1, TreeNode<Integer> node2) {
		if (root == null)
			return null;
		if (root == node1 && root == node2)
			return root;
		TreeNode<Integer> leftResult = findCommonAncestorHelper(root.left,
				node1, node2);
		if (leftResult != null && leftResult != node1 && leftResult != node2)
			return leftResult;

		TreeNode<Integer> rightResult = findCommonAncestorHelper(root.right,
				node1, node2);
		if (leftResult != null && leftResult != node1 && leftResult != node2)
			return leftResult;
		if (leftResult != null && rightResult != null)
			return root;
		else if (root == node1 || root == node2)
			return root;
		else
			return leftResult == null ? rightResult : leftResult;
	}

}