Lowest Common Ancestor of a Binary Tree
Last Updated: March 29, 2026
Understanding the Problem
We have a binary tree (not a BST, just 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.
So the key question becomes: how do we figure out where p and q are relative to any given node? The answer is recursive exploration. For each node, we check whether p or q exists in its left subtree, its right subtree, or if 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 our 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
The most natural way to think about this problem is with recursion. Picture yourself standing at any node in the tree. You want to know: does p live somewhere below me on the left? Does q live somewhere below me on the right? Or am I one of them?
Here's the key insight: if we do a DFS and propagate "found" signals upward, the LCA is the first node where signals arrive from both sides. Concretely, 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 must be the LCA because
pis on one side andqis on the other. - If only one side returns non-null, that means 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 must be somewhere below (guaranteed by the problem), so this node is the LCA.
That last point is subtle but important. When we find p, we return it without searching further down. Why? Because if q is below p, then p is the LCA. And if q is in a completely different branch, the recursion will find it there and the merging logic at a higher ancestor will handle it.
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 is elegant and efficient, but it uses the call stack implicitly. What if we separated the two concerns: first build a way to trace paths, then find where the paths diverge?
Approach 2: Iterative with Parent Pointers
Intuition
Here's a completely different way to think about the problem. If you had a way to walk upward from any node to the root (like following parent pointers), finding the LCA is straightforward: 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 doesn't give us parent pointers by default, but we can build them ourselves. A single BFS from the root lets us record each node's parent in a hash map. Once we have that, we trace p's ancestors into a set, then walk q upward until we hit a node that's already in that set. That node is the LCA.
This approach separates the problem into two clean steps: (1) build parent pointers, (2) find the intersection of ancestor paths. It's more intuitive to reason about and avoids recursion entirely, which means no risk of stack overflow.
Think of the ancestor path from any node to the root as a chain. The LCA is the deepest point where the chains from p and q merge into a single path. By collecting all of p's ancestors into a set and then walking q upward, we're guaranteed to hit this merge point. The first ancestor of q that also appears in p's chain is, by definition, the lowest common ancestor.
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).