Problem Overview
LeetCode 236 — Lowest Common Ancestor of a Binary Tree — gives you the root of a binary tree and two nodes p and q, and asks you to find their lowest common ancestor. The LCA is defined as the deepest node in the tree that is an ancestor of both p and q. A node is considered an ancestor of itself.
This problem is labeled Medium and is one of the most frequently asked tree questions in technical interviews. Unlike LeetCode 235 which restricts the input to a BST, LeetCode 236 works on a general binary tree with no ordering guarantees — the approach must be fundamentally different.
The constraints ensure both p and q are guaranteed to exist in the tree and all node values are unique. These guarantees simplify the solution considerably because you never need to handle the case where a target node is missing.
- Input: root of binary tree and two nodes p and q
- Output: their lowest common ancestor node
- LCA is the deepest node that is an ancestor of both
- A node can be its own ancestor
- Both p and q are guaranteed to exist in the tree
- All node values are unique
LCA of BST vs Binary Tree
In a BST (LeetCode 235), the ordering property lets you navigate with simple value comparisons: if both p and q are less than the current node, recurse left; if both are greater, recurse right; otherwise the current node is the LCA. This runs in O(h) time with no need to explore both subtrees.
A general binary tree has no such ordering. You cannot determine which subtree contains p or q without actually searching. The correct approach is post-order DFS — process left and right children first, then make a decision at the current node based on what both subtrees report back.
Post-order traversal naturally solves LCA because information bubbles up from the leaves toward the root. The first node where both the left and right subtrees report finding a target is the deepest possible ancestor of both — the LCA by definition.
The Recursive Insight
The recursive solution is elegant: if a node is p or q, return it immediately. After recursing left and right, if both return non-null the current node is the LCA. If only one returns non-null, that result propagates upward — both targets are in the same subtree.
Recursive Algorithm
The base case handles two situations: if the current node is null, return null (we have fallen off the tree); if the current node is p or q, return the current node immediately (we found a target, no need to look deeper — the node could be an ancestor of the other target).
After the base case, recurse into both subtrees: left = lca(node.left, p, q) and right = lca(node.right, p, q). The key decision is then made: if both left and right are non-null, p and q were found in different subtrees, so the current node is their LCA — return it.
If only left is non-null, both targets were found in the left subtree and the result propagates up. If only right is non-null, both targets were found in the right subtree. If both are null, neither target exists below this node — return null.
- 1Base case: if node is null, return null
- 2Base case: if node is p or q, return node
- 3left = lowestCommonAncestor(node.left, p, q)
- 4right = lowestCommonAncestor(node.right, p, q)
- 5If both left and right are non-null: return node (current node is LCA)
- 6If only left is non-null: return left
- 7If only right is non-null: return right
- 8If both null: return null
Why This Works
Post-order processing ensures that by the time we inspect a node, we already know what both subtrees found. The algorithm exploits this: the first node in the traversal where both subtrees return a non-null value is necessarily the deepest node that has both p and q in its subtree — the LCA.
If both p and q are in the same subtree, the deeper ancestor is what gets returned first and propagates all the way up. The other subtree returns null at every level, so only one side is ever non-null above the actual LCA. The result bubbles up correctly without interference.
The time complexity is O(n) because in the worst case every node must be visited. The space complexity is O(h) where h is the height of the tree, due to the recursion stack. For a balanced tree h = O(log n); for a skewed tree h = O(n).
A Node Can Be Its Own Ancestor
If p is an ancestor of q, then p itself is the LCA. The base case handles this correctly: when we reach p, we return it immediately without searching deeper. The subtree rooted at p contains q, but we never need to find it — returning p is correct because p is the deepest common ancestor.
Iterative with Parent Pointers
An iterative approach builds a parent pointer map using BFS or DFS. Traverse the entire tree and for each node record its parent. Stop early if both p and q have been found in the traversal queue to avoid unnecessary work.
Once the parent map is built, trace the ancestors of p by walking up through the map until reaching the root, collecting each ancestor into a set. Then walk up from q using the parent map, and the first node encountered that is already in p's ancestor set is the LCA.
This approach runs in O(n) time and O(n) space for both the parent map and the ancestor set. It is more code than the recursive solution and uses more memory, but it avoids potential stack overflow on very deep trees where recursion depth could exceed system limits.
- 1BFS/DFS to build parent map: parent[node] = parentNode for all nodes
- 2Stop traversal early once both p and q are found
- 3Walk up from p: add p and all its ancestors to a set
- 4Walk up from q: for each ancestor check if it is in p's ancestor set
- 5The first match is the LCA — return it
Code Walkthrough Python and Java
Python recursive solution: def lowestCommonAncestor(root, p, q). If not root or root == p or root == q: return root. left = self.lowestCommonAncestor(root.left, p, q). right = self.lowestCommonAncestor(root.right, p, q). Return root if left and right else left or right. That is the complete solution — 6 lines of logic, O(n) time O(h) space.
Java recursive solution mirrors this structure exactly: guard clause returns root when null or when root equals p or q; then recurse left and right; return root if both non-null, otherwise return whichever is non-null. The TreeNode class is provided by LeetCode — no imports needed beyond the class definition.
Both solutions handle all edge cases: p is an ancestor of q (returned at base case), q is an ancestor of p (returned at base case), p and q are in different subtrees (caught by the both non-null condition), and the tree has only two nodes (one base case hit, one recursion returns null).
Both Targets Must Exist
The problem guarantees both p and q exist in the tree. If that guarantee were removed, this solution would be incorrect — it returns a node whenever it finds p or q, even if the other is absent. Without the guarantee you must track whether both were actually found and return null if not.