CC_4_7

CommonAncestor.java

// 4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. 
// Avoid storing additional nodes in a data structure. 
// NOTE: This is not necessarily a binary search tree.
class Node {
	public int val;
	public Node left;
	public Node right;
	public Node(int val) {
		this.val = val;
		left = null;
		right = null;
	}
}
class CommonAncestor {
	public static Node findCommonAncestor(Node root, Node a, Node b) {
		if (a == b) return a;
		if (root == null) return null;
		Node ans = new Node(0);
		findCommonAncestorHelper(root, a, b, ans);
		return ans.right;
	}
	public static int findCommonAncestorHelper(Node root, Node a, Node b, Node ans) {
		if (root == null) return 0;
		int found = findCommonAncestorHelper(root.left, a, b, ans) + findCommonAncestorHelper(root.right, a, b, ans);
		if (found > 1) {
			// two founded
			ans.right = root;
			return Integer.MIN_VALUE;
		}
		if (root == a || root == b) {
			if (found > 0) {
				ans.right = root;
				return Integer.MIN_VALUE;
			} else {
				return found+1;	
			}	
		} 
		return found;

	}
	public static void main(String[] args) {
		Node root = new Node(0);
		root.left = new Node(1);
		root.right = new Node(2);
		root.left.right = new Node(3);
		root.left.left = new Node(4);
		root.right.right = new Node(5);
		root.right.left = new Node(6);

		assert findCommonAncestor(root, root, root.left) == root;
		assert findCommonAncestor(root, root.left, root.right) == root;
		assert findCommonAncestor(root, root.left.left, root.right.right) == root;
		assert findCommonAncestor(root, root.left.left, root.left.right) == root.left;
		assert findCommonAncestor(root, root.left.left, root.left) == root.left;

		System.out.println("Tests Passed");
	}
}