Approach Summary
If both p and q are smaller than root, LCA is in left subtree. If both larger, right subtree. Otherwise root is the LCA.
Practice Mode
3 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: BST Property Directed Walk (Optimal) | O(h) | O(1) | Walk left if both values are smaller; walk right if both are larger; split point is LCA. |
| 2 Approach 2: Recursive Divide and Conquer (Optimal) | O(h) | O(h) | Recursively walks the tree, steering left or right depending on whether p and q both lie in the same subtree. |
| 3 Approach 2: Recursive Divide and Conquer (Optimal) | O(h) | O(h) | Recursively walks the tree, steering left or right depending on whether p and q both lie in the same subtree. |
Step 1: Baseline
Approach 1: BST Property Directed Walk (Optimal)
Time: O(h)
Space: O(1)
Because a BST partitions values strictly, if both p and q are less than current node, their LCA must be in the left subtree. If both are greater, their LCA must be in the right subtree. The first node where p and q diverge (or match current node) is the unique LCA.
Approach 1: BST Property Directed Walk (Optimal) Implementation
Approach 1: BST Property Directed Walk (Optimal)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode curr = root;
while (curr != null) {
if (p.val < curr.val && q.val < curr.val) curr = curr.left;
else if (p.val > curr.val && q.val > curr.val) curr = curr.right;
else return curr;
}
return null;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* curr = root;
while (curr) {
if (p->val < curr->val && q->val < curr->val) curr = curr->left;
else if (p->val > curr->val && q->val > curr->val) curr = curr->right;
else return curr;
}
return NULL;
}
};class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
curr = root
while curr:
if p.val < curr.val and q.val < curr.val:
curr = curr.left
elif p.val > curr.val and q.val > curr.val:
curr = curr.right
else:
return currfunction lowestCommonAncestor(root, p, q) {
let curr = root;
while (curr) {
if (p.val < curr.val && q.val < curr.val) curr = curr.left;
else if (p.val > curr.val && q.val > curr.val) curr = curr.right;
else return curr;
}
} Step 2
Approach 2: Recursive Divide and Conquer (Optimal)
Time: O(h)
Space: O(h)
If both p and q have values strictly less than root.val, the LCA must lie in the left subtree. If both are strictly greater, LCA must lie in the right subtree. Otherwise, root is the split point and the LCA.
Approach 2: Recursive Divide and Conquer (Optimal) Implementation
Approach 2: Recursive Divide and Conquer (Optimal)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return rootfunction lowestCommonAncestor(root, p, q) {
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
} Step 2: Most Optimized
Approach 2: Recursive Divide and Conquer (Optimal)
Time: O(h)
Space: O(h)
If both p and q have values strictly less than root.val, the LCA must lie in the left subtree. If both are strictly greater, LCA must lie in the right subtree. Otherwise, root is the split point and the LCA.
Approach 2: Recursive Divide and Conquer (Optimal) Implementation
Approach 2: Recursive Divide and Conquer (Optimal)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
return root;
}
};class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return rootfunction lowestCommonAncestor(root, p, q) {
if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
return root;
}Edge Cases to Watch
- One of the nodes is the ancestor of the other (e.g. root is p or q; returns that node directly)
- Nodes are immediate children of root
- Nodes reside on opposite sides of root
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- LCA in BST using BST property
Complexity Analysis
Time Complexity
O(h)
Space Complexity
O(1)
Tags
Tree DFS BST
Frequently Asked Questions
What is the optimal time and space complexity for Lowest Common Ancestor of a BST?
The optimal solution for Lowest Common Ancestor of a BST achieves O(h) runtime complexity and requires O(1) auxiliary space. Time complexity is O(h) where h is tree height (O(log n) for balanced BST, O(n) for skewed). Space complexity is O(1) iterative or O(h) recursive.
How do I identify that Lowest Common Ancestor of a BST requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: LCA in BST using BST property. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Lowest Common Ancestor of a BST?
Essential edge cases to verify include: One of the nodes is the ancestor of the other (e.g. root is p or q; returns that node directly); Nodes are immediate children of root; Nodes reside on opposite sides of root. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Lowest Common Ancestor of a BST?
Lowest Common Ancestor of a BST is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, LinkedIn.