Lowest Common Ancestor of a Binary Tree

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return LCAHeper(root, p, q).ancestor;
    }

    // return an object consisting of an int and a node. The int field is
    // 0, 1, 2 depending on how many nodes{p,q} are present
    // if both are presented
    // ancestor is assigned to a non-null value.
    public Status LCAHeper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return new Status(0, null);

        Status left = LCAHeper(root.left, p, q);
        if (left.numTragetedNodes == 2) return left;

        Status right = LCAHeper(root.right, p, q);
        if (right.numTragetedNodes == 2) return right;        

        int numTragetedNodes = left.numTragetedNodes + right.numTragetedNodes + (root == p ? 1 : 0) + (root == q ? 1 : 0);
        return new Status(numTragetedNodes, numTragetedNodes == 2 ? root : null);
    }
}

class Status {
    int numTragetedNodes;
    TreeNode ancestor;

    public Status(int numTragetedNodes, TreeNode ancestor) {
        this.numTragetedNodes = numTragetedNodes;
        this.ancestor = ancestor;
    }
}

Time complexity:

First, just for fun, we assume that the tree contains n nodes and is balanced (with its height equals to log(n) ). In this case, the run time complexity would be O(n). Most people would guess a higher ordered complexity than O(n) due to the function countMatchesPQ() traverses the same nodes over and over again. Notice that the tree is balanced, you cut off half of the nodes you need to traverse in each recursive call of LCA() function. The proof that the complexity is indeed O(n) is left as an exercise to the reader.

What if the tree is not necessarily balanced? Then in the worst case the complexity could go up to O(n^2). Why? Could you come up with such case? (Hint: The tree might be a degenerate tree).

Follow up: what if the node has a pointer to the parent node.

Solution1:

As we trace the two paths from both nodes up to the root, eventually it will merge into one single path. The LCA is the exact first intersection node where both paths merged into a single path. An easy solution is to use a hash table which records visited nodes as we trace both paths up to the root. Once we reached the first node which is already marked as visited, we immediately return that node as the LCA.

Time and space complexity: O(h), where h is the height of the tree.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Set<TreeNode> visited = new HashSet();

    while (p || q) {
        if (p) {
            if (visited.contains(p)) {
                return p;
            }
            visited.add(p);
            p = p.parent;
        }
        if (q) {
            if (visited.contains(q)) {
                return q;
            }
            visited.add(q);
            q = p.parent;
        }    
    }

    return null;
}

Solution 2:

A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is always dh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?

The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes. If not, one of the node would eventually reach NULL (root’s parent), which we conclude that both nodes are not in the same tree. However, that part of code shouldn’t be reached, since the problem statement assumed that both nodes are in the same tree.

int getHeight(Node *p) {
  int height = 0;
  while (p) {
    height++;
    p = p->parent;
  }
  return height;
}

// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
  int h1 = getHeight(p);
  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.
  int dh = h2 - h1;
  for (int h = 0; h < dh; h++)
    q = q->parent;
  while (p && q) {
    if (p == q) return p;
    p = p->parent;
    q = q->parent;
  }
  return NULL;  // p and q are not in the same tree
}