Lowest Common Ancestor of a Binary Search Tree
Problem
Given the root of a binary search tree (BST) and two nodes p and q, return the lowest common ancestor (LCA) of nodes p and q in the BST.
- The number of nodes in the tree is in the range [2, 10⁵]
- −10⁹ ≤ Node.val ≤ 10⁹
- All Node.val are unique
- p != q
- p and q will exist in the BST
Example
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 86Starting at the root node with value 6, both p (2) and q (8) are on different sides: p is less than 6, q is greater than 6. This means 6 is the split point where the paths to p and q diverge, so 6 is their lowest common ancestor. If both p and q were less than 6, the search would continue left; if both were greater, it would continue right.
Approach
Straightforward Solution
A brute-force approach would be to find the paths from the root to p and q separately, then compare these paths to find the last common node. This requires extra space and time proportional to the height of the tree, and is less efficient.
Core Observation
In a BST, for any node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This property allows directed traversal to find the LCA by comparing p and q values to the current node.
Path to Optimal
PreviewThe key insight is that the BST property allows a single traversal from the root to find the LCA without storing paths. If both p and q are greater than the current node, the LCA must be in the right subtree; if both are less, it must be in the left subtree…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewStart from the root and iterate down the tree. At each node, compare p…
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(h)
Each step moves down one level of the BST, and the height h is at most O(log n) for balanced trees or O(n) in the worst case. The algorithm visits at most h nodes.
Space
O(1)
The solution uses only a constant amount of extra space for pointers and variables, with no recursion or auxiliary data structures.
Pattern Spotlight
Binary Search (Directed Tree Traversal)
Use the BST property to guide traversal towards the LCA by moving in the direction where both target nodes lie; the first node where they split paths is the LCA.
Solution
| 1 | class Solution:
|
| 2 | def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
|
| 3 | curr = root
|
| 4 |
|
| 5 | while curr:
|
| 6 | if p.val > curr.val and q.val > curr.val:
|
| 7 | curr = curr.right
|
| 8 | elif p.val < curr.val and q.val < curr.val:
|
| 9 | curr = curr.left
|
| 10 | else:
|
| 11 | return curr |
Step-by-Step Solution
Traverse BST to Narrow Down LCA by Comparing Node Values
| 3 | curr = root
|
| 5 | while curr:
|
| 6 | if p.val > curr.val and q.val > curr.val:
|
| 7 | curr = curr.right
|
| 8 | elif p.val < curr.val and q.val < curr.val:
|
| 9 | curr = curr.left
|
| 10 | else:
|
| 11 | return curr |
Objective
To iteratively move down the BST towards the LCA by leveraging the relative values of p and q compared to the current node.
Key Insight
The BST property allows pruning half of the tree at each step. If both p and q are greater than the current node, the LCA must be in the right subtree; if both are smaller, it must be in the left subtree. This directed search avoids unnecessary exploration and leads directly to the LCA without extra space.
Interview Quick-Check
Core Logic
At each node, decide traversal direction by comparing p.val and q.val with the current node's value; move left if both are smaller, right if both are larger, else return current node.
State & Boundaries
The loop continues while the current node is not null, ensuring traversal stops when the LCA is found or the tree ends.
Common Pitfalls & Bugs
Failing to handle the case where one of p or q equals the current node's value can cause incorrect traversal or missed LCA.
Complexity
This approach guarantees O(h) time complexity and O(1) auxiliary space, optimal for BST LCA problems.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
else:If neither of the above conditions hold, return the current node as the LCA.
This condition captures the split point where p and q diverge into different subtrees or one equals the current node, which by definition is the lowest common ancestor.
if p.val > curr.val and q.val > curr.val:Check if both p and q have values greater than the current node's value.
If both target nodes are greater, the LCA cannot be the current node or in the left subtree, so the search moves right to narrow down the candidate.
elif p.val < curr.val and q.val < curr.val:Check if both p and q have values less than the current node's value.
If both target nodes are smaller, the LCA must be in the left subtree, so the search moves left to continue narrowing the candidate.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why does the first node where p and q values diverge in relation to the current node's value represent the lowest common ancestor?
See the answer with Pro.
Related Problems
Modified Binary Search pattern
Don't just read it. Drill it.
Reconstruct Lowest Common Ancestor of a Binary Search 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 Search Tree drill