Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes5and1is3. Another example is LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.

Solution:

There are only 4 types of situation if a lowest common ancestor exists:

1. One target nodes is on the left sub tree tree of the LCA, and the other one is on the right sub tree of the LCA.
2. Both target nodes are on the left sub tree of the LCA.
3. Both target nodes are on the right sub tree of the LCA.
4. The LCA its self is one of the target nodes.

For this question, since LCA is guaranteed to exist. So, when we have met either of the target nodes, we can simply return the current root, this will cover condition 2, 3, and 4. For condition 1, we use divide and conquer to search for LCA of the two nodes on left and right subtrees, if both find, return current root.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return null;
    }
    if (root == p || root == q) {
        return root;
    }
    TreeNode left  = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root;
    }
    if (left != null) {
        return left;
    }
    if (right != null) {
        return right;
    }
    return null;
}