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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Approach: Recursive Search (Optimal Solution)

Algorithm

1. If the current node is null, or equals p or q, return it
2. Recursively search the left and right subtrees, recording the results as left and right
3. If both left and right are non-null, the current node is the LCA
4. Otherwise, return whichever of left and right is non-null

Key Insight

The recursion “bubbles up” the found node. If one subtree finds p and the other finds q, the node where the two paths meet is the LCA. If only one subtree returns a node, that node is the ancestor of the other (possibly via the “descendant of itself” rule), so it propagates upward.

Time & Space Complexity

• Time Complexity: O(n) - every node may be visited once in the worst case
• Space Complexity: O(n) - recursion stack in the worst case (a skewed tree)

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class LowestCommonAncestor {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || 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;
        }
        return left != null ? left : right;
    }
}

Example Walkthrough

For root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4:

1. At node 3, search left subtree (rooted at 5) and right subtree (rooted at 1)
2. In the left subtree, node 5 itself equals p, so it returns 5 immediately
3. In the right subtree, searching for 4 finds it under node 2’s right child → returns node 4 upward
4. Node 3 receives left=5 and right=4 (well, right returns node 4 or node 2 depending on path — both non-null and in opposite subtrees)
5. Both sides are non-null, so node 3 is the LCA — wait, let’s trace more carefully below

For p = 5, q = 4:

1. lowestCommonAncestor(3, 5, 4): left = LCA(5’s subtree) = 5; right = LCA(1’s subtree) → 1’s left (0) and right (8) both return null, so right = null. Both not non-null, return left = 5
2. Actually with p=5, q=4: right subtree (rooted at 1) contains neither 5 nor 4, so LCA(1) = null. left subtree returns 5. Since right is null, the answer propagates 5 up
3. Result: 5 — correct, since 4 is a descendant of 5 and a node can be its own ancestor

Key Insights

1. Post-order Search: Both subtrees are fully explored before the current node is decided
2. Descendant of Itself: A node can be its own LCA when one of p/q is an ancestor of the other
3. Unique Values: Values are unique and p, q are guaranteed present, so reference equality is sufficient
4. Single Pass: No parent pointers or path storage are needed — the recursion handles everything

The recursive solution is the optimal approach, providing O(n) time and O(n) space.