Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the Lowest Common Ancestor (LCA) of two given nodes p and q.

The LCA is defined as the deepest node that has both p and q as descendants (a node can 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: 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: LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.

Constraints:

2 <= Number of nodes <= 10⁵
All node values are unique.
p != q; both p and q exist in the tree.

Solution: Recursive DFS
Complexity Analysis

Solution: Recursive DFS

The key observations:

If the current node is null, return null.
If the current node is p or q, return the current node immediately (it is the LCA if the other is a descendant, or we'll find the true LCA higher up).
Recurse into both subtrees. If both return non-null, the current node is the LCA (p and q are in different subtrees).
If only one side returns non-null, propagate that result upward.

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;

    // If root is p or q, it is the LCA (or will propagate up)
    if (root == p || root == q) return root;

    TreeNode left  = lowestCommonAncestor(root.left,  p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // p found in one subtree, q in the other — current node is LCA
    if (left != null && right != null) return root;

    // Both in same subtree — propagate the found node up
    return left != null ? left : right;
}

Trace for Example 1 (p=5, q=1):

At node 3: recurse left (returns 5) and right (returns 1) → both non-null → return 3 ✓
At node 5: root == p → return 5 immediately
At node 1: root == q → return 1 immediately

Complexity Analysis

Time: O(n). Visits each node at most once.
Space: O(h). Recursion stack depth (O(log n) balanced, O(n) skewed).