Lowest Common Ancestor

Given a binary tree and two nodes. Find Least Common Ancestor (LCA) of the two nodes.

For example given the tree T below. LCA(T, 5, 6) = 3, LCA(T, 4, 6) = 1, etc.

                             1
                          /      \
                         2        3
                      /         /   \
                     4         5     6
                       \           /
                        7         8

With parent pointer
If we are given parent pointer for each node then the problem is pretty simple. Observe that if the nodes are in same level then we could easily find the LCA by traversing up one parent at a time for both of the nodes and when the parents are same then the parent is the LCA. But what if the nodes are not in the same level? Idea is to bring the deeper node to the same level as the shallower node. For example, when finding LCA(5, 8) we can see 5 is at level 2 and 8 us at level 3. Difference in level is 3-2=1. So, we can move node 8 to one parent up (node 6) and the try the simple LCA(5,6) by moving both the nodes one parent up at a time and check if parents meet. Below is a simple code with O(lgn) for balanced tree or O(n) for unbalanced tree.

public static void swap(TreeNode a, TreeNode b) {
    final TreeNode temp = a;
    a = b;
    b = temp;
}

public static void swap(int a, int b) {
    final int temp = a;
    a = b;
    b = temp;
}

public static int getHeight(TreeNode p) {
    int height = 0;
    while (p != null) {
        height++;
        p = p.parent;
    }
    return height;
}

// As root->parent is NULL, we don't need to pass root in.
TreeNode LCA(TreeNode p, TreeNode q) {
    final int h1 = getHeight(p);
    final int h2 = getHeight(q);
    // swap both nodes in case p is deeper than q.
    if (h1 > h2) {
        swap(h1, h2);
        swap(p, q);
    }
    // invariant: h1 <= h2.
    final int dh = h2 - h1;
    for (int h = 0; h < dh; h++) {
        q = q.parent;
    }
    while (p != null && q != null) {
        if (p == q) {
            return p;
        }
        p = p.parent;
        q = q.parent;
    }
    return null; // p and q are not in the same tree
}

Without parent pointer
One first idea is to start from the root and recursively traverse down until we hit ether of the nodes then-

1. If we found both nodes in the left subtree then recurse the above procedure starting from the left child of root.
2. Else if, we found both nodes in the right subtree then recurse the above procedure starting from the right child of root.
3. Else if we found one on left and other on right then return root.
4. else if we didn’t find one or both then return null.

This above algorithm is a top down approach and the search spaces are overlapping i.e. we are traversing some part of the tree many times. We can skip overlapping search space by traversing from  bottom up as follows.

1. While traversing from the bottom recursively if we reach a one of the given nodes, we pass it up to its parent.
2. Then we will check from the parent whether either of the nodes is in left or right subtree.
3. If it is then the parent must be the LCA. We pass its parent up to the root.
4. If not then we pass up to the parent the root of the subtree (left or right) node which contains either one of the two nodes, or NULL if neither subtree contains the nodes .

public static BTNode LCA(BTNode root, BTNode x, BTNode y) {
	  if (root == null) return null;
	  if (root == x || root == y) return root;

	  BTNode leftSubTree = LCA(root.left, x, y);
	  BTNode rightSubTree = LCA(root.right, x, y);

	  //x is in one subtree and and y is on other subtree of root
	  if (leftSubTree != null && rightSubTree != null) return root;  
	  //either x or y is present in one of the subtrees of root or none present in either side of the root
	  return leftSubTree!=null ? leftSubTree : rightSubTree;  
}

LCA of BST
However finding LCA for BST is rather simple then a simple binary tree sue to the BST property of left<root

public static TreeNode LowestCommonAnchestorBST(TreeNode root, final TreeNode p, final TreeNode q) {
    if (root == null) {
        return null;
    }

    while (root != null) {
        if (root.key > p.key && root.key > q.key) {
            root = root.left;
        } else if (root.key < p.key && root.key < q.key) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
}