Lowest Common Ancestor of a Binary Tree
Understanding the Problem
We have a binary tree (not a BST, a regular binary tree with no ordering guarantees) and two nodes, p and q, that are guaranteed to exist somewhere in it. We need to find their lowest common ancestor, the deepest node that has both p and q in its subtree (including itself).
What makes this different from the BST version (LeetCode #235) is that we can't use value comparisons to navigate. In a BST, we know exactly which direction to search based on node values. Here, p and q could be anywhere. A node with value 5 might be in the right subtree of a node with value 8. There's no ordering to exploit.
To find where p and q sit relative to any given node, we explore recursively. For each node, we check whether p or q exists in its left subtree, its right subtree, or whether the node itself is one of them. The first node we encounter going bottom-up that has p on one side and q on the other (or is one of them with the other below it) is the LCA.
Key Constraints:
[2, 10^5]nodes -> We need O(n) or better. Anything that visits each node a constant number of times is fine.-10^9 <= Node.val <= 10^9-> Large values, but we only compare node references (not values) in the core algorithm, so no overflow concerns.- All values are unique -> This helps with identification but doesn't change our algorithm since we compare node references, not values.
pandqexist in the tree -> We don't need to handle "not found" cases. The LCA is guaranteed to exist.
Approach 1: Recursive DFS
Intuition
A single DFS that propagates "found" signals upward locates the LCA: it is the first node where signals arrive from both sides. We write a recursive function that returns a node if it finds p or q in the subtree, or null if neither is there. Then:
- If both left and right subtrees return non-null results, the current node is the LCA, because
pis on one side andqis on the other. - If only one side returns non-null, both
pandqare in that subtree, so we pass the result upward. - If the current node itself is
porq, we return it immediately. The other node is somewhere below or in a sibling subtree, so this node either is the LCA or sits below it.
The early return when a node equals p or q deserves a justification. When we find p, we return it without searching further down. If q is below p, then p is the LCA, and returning p is correct. If q is in a different branch, the recursion finds it there, and a higher ancestor sees a non-null result from both sides and reports itself as the LCA.
Algorithm
- If the current node is null, return null (base case: we've gone past a leaf).
- If the current node is
porq, return the current node. - Recursively search the left subtree.
- Recursively search the right subtree.
- If both recursive calls return non-null, the current node is the LCA, so return it.
- If only one side returns non-null, return that result (the LCA is deeper in that direction).
Example Walkthrough
Code
- Time Complexity: O(n). In the worst case, we visit every node in the tree exactly once. Each node does O(1) work, so the total is O(n).
- Space Complexity: O(n). The recursion stack can grow as deep as the height of the tree. For a balanced tree that's O(log n), but for a completely skewed tree the height is n, making the space O(n).
The recursive approach relies on the call stack to hold ancestor information. The next approach makes that information explicit by recording each node's parent, then finding where the two ancestor paths meet.
Approach 2: Iterative with Parent Pointers
Intuition
If we could walk upward from any node to the root by following parent pointers, finding the LCA reduces to a path-intersection problem: trace the path from p to the root, trace the path from q to the root, and find the deepest node that appears in both paths.
The tree has no parent pointers by default, so we build them. A BFS from the root records each node's parent in a hash map. We then trace p's ancestors into a set and walk q upward until we reach a node already in that set. That node is the LCA.
This splits the problem into two steps: build parent pointers, then find the intersection of ancestor paths. It uses no recursion, so it avoids stack overflow on a deeply skewed tree.
The ancestor path from each node to the root forms a single chain. The chains from p and q share a suffix that ends at the root, and the LCA is the deepest node in that shared suffix. Collecting all of p's ancestors into a set and walking q upward stops at the first node on q's chain that also lies on p's chain, which is exactly that deepest shared node.
Algorithm
- Start a BFS from the root. For each node, store its parent in a hash map.
- From
p, walk upward using the parent map, adding each ancestor to a set (includingpitself). - From
q, walk upward using the parent map. The first node that already exists in the ancestor set is the LCA.
Example Walkthrough
Code
- Time Complexity: O(n). Building the parent map visits each node once via BFS. Tracing ancestors and walking q upward are both O(h). Total: O(n).
- Space Complexity: O(n). The parent map stores one entry per node. The ancestors set stores at most h entries. The dominant term is the parent map: O(n).