Lowest Common Ancestor of a Binary Tree
Problem
Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA), defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).
- The number of nodes in the tree is in the range [2, 10⁵]
- −10⁹ ≤ Node.val ≤ 10⁹
- All Node.val are unique
- p and q are different nodes and both exist in the tree
Example
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13Starting at the root (3), the algorithm recursively searches left and right subtrees for nodes p=5 and q=1. It finds p in the left subtree and q in the right subtree. Since both subtrees contain one of the nodes, the root (3) is the lowest common ancestor. The critical moment is when both left and right recursive calls return non-null, indicating the current node is the LCA.
Approach
Straightforward Solution
A brute-force approach might store parent pointers or paths from root to p and q, then compare paths to find the last common node. This requires extra space and multiple traversals.
Core Observation
The LCA of two nodes p and q is the lowest node in the tree whose left and right subtrees contain p and q respectively, or the node itself is p or q. This naturally suggests a recursive exploration of the tree to find p and q in subtrees.
Path to Optimal
PreviewThe key insight is to use a single DFS traversal that returns the node if it matches p or q, or returns the LCA if found in subtrees. If both left and right recursive calls return non-null, the current node is the LCA…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewPerform a recursive DFS starting at root. If the current node is null, return null…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each node is visited once during the DFS traversal, resulting in linear time proportional to the number of nodes.
Space
O(h)
The recursion stack uses space proportional to the height of the tree, which is O(h). This is auxiliary space excluding the input tree.
Pattern Spotlight
DFS (Postorder Traversal for State Propagation)
When searching for nodes in a tree to find a common ancestor, use DFS to propagate found nodes upward; the first node where both left and right subtrees report findings is the lowest common ancestor.
Solution
| 1 | class Solution: |
| 2 | def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode": |
| 3 | if not root: |
| 4 | return None |
| 5 | |
| 6 | if root == p or root == q: |
| 7 | return root |
| 8 | |
| 9 | left = self.lowestCommonAncestor(root.left, p, q) |
| 10 | right = self.lowestCommonAncestor(root.right, p, q) |
| 11 | |
| 12 | if left and right: |
| 13 | return root |
| 14 | |
| 15 | return left if left else right |
Step-by-Step Solution
Return Null for Empty Subtrees to Signal Absence
| 3 | if not root: |
| 4 | return None |
Objective
To terminate recursion when reaching a null node, indicating p or q is not found in this path.
Key Insight
Returning null for empty subtrees is essential to signal that neither p nor q exists below this node. This base case prevents unnecessary traversal and allows the recursion to correctly propagate findings upward.
Interview Quick-Check
Core Logic
Returning null on a null node ensures the recursion correctly identifies absence of p and q in that subtree.
State & Boundaries
This base case is the stopping condition for the recursion.
Return Current Node When It Matches p or q
To identify when the current node is one of the targets and propagate it upward as a potential ancestor.
Recursively Search Left and Right Subtrees for Targets
To explore both subtrees to find nodes p and q and gather information about their locations.
Identify LCA When Both Subtrees Contain Targets
To determine that the current node is the LCA if p and q are found in different subtrees.
Propagate Non-null Subtree Result Upwards
To continue propagating the found target node or LCA upwards when only one subtree contains p or q.
4 more steps with full analysis available on Pro.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if left and right:Check if both left and right recursive calls found targets.
This condition detects the critical moment when p and q are found in separate subtrees, identifying the current node as the LCA.
return rootReturn the current node as the LCA when both sides are non-null.
Returning the current node here finalizes the discovery of the lowest common ancestor, as it is the deepest node connecting p and q.
if root == p or root == q:Check if the current node matches p or q.
Identifying p or q at the current node is critical to mark the presence of one of the targets in this subtree, enabling correct ancestor detection.
Full line-by-line criticality + rationale for all 9 lines available on Pro.
Test Your Understanding
Why does returning the current node when both left and right recursive calls are non-null guarantee the lowest common ancestor?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Lowest Common Ancestor of a Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Lowest Common Ancestor of a Binary Tree drill