Lowest Common Ancestor of a Binary Search Tree
Description
Given the root of a Binary Search Tree (BST) and two nodes p and q, find their Lowest Common Ancestor (LCA).
The Lowest Common Ancestor of two nodes is the deepest node in the tree that has both p and q as descendants. A node is allowed to be a descendant of itself — so if p is an ancestor of q, then p itself is the LCA.
Recall that a BST has a special ordering property: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This property is key to solving this problem efficiently.
Examples
Example 1
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6
Explanation: Node 2 sits in the left subtree of 6, and node 8 sits in the right subtree of 6. Since 2 and 8 are on opposite sides of node 6, the deepest node that is an ancestor of both is 6 itself. No node deeper than 6 can have both 2 and 8 as descendants because the BST property forces them into different subtrees at node 6.
Example 2
Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Explanation: Node 4 is a child of node 2 (sitting in 2's right subtree). Since a node can be a descendant of itself, node 2 is the LCA because it is an ancestor of both itself and node 4. Going deeper than node 2 would lose node 2 as a descendant.
Example 3
Input: root = [2, 1], p = 2, q = 1
Output: 2
Explanation: The tree has only two nodes: root 2 with left child 1. Node 2 is the ancestor of node 1, and a node counts as its own descendant, so the LCA is 2.
Constraints
- The number of nodes in the tree is in the range [2, 10^5]
- -10^9 ≤ Node.val ≤ 10^9
- All Node.val are unique
- p ≠ q
- p and q will exist in the BST
Editorial
Brute Force
Intuition
Forget that this is a BST for a moment — treat it as a plain binary tree. To find the LCA of two nodes in any binary tree, one straightforward strategy is to find the path from the root to each of the two target nodes, then compare the two paths side by side.
Imagine you have two friends living in different parts of a city, and you want to find the last intersection they both pass through when driving from the city center. You trace each friend's route from the center to their home, then walk along both routes together until they diverge. The last shared point is your answer.
Similarly, we record the path from root to p and the path from root to q. We then compare both paths element by element. The last node that appears in both paths is the LCA.
Step-by-Step Explanation
Let's trace through with the tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4:
Step 1: Find the path from root (6) to node p (2).
- Start at root 6. Is 6 == 2? No.
- 2 < 6, so go left to node 2. Is 2 == 2? Yes!
- Path to p: [6, 2]
Step 2: Find the path from root (6) to node q (4).
- Start at root 6. Is 6 == 4? No.
- 4 < 6, so go left to node 2. Is 2 == 4? No.
- 4 > 2, so go right to node 4. Is 4 == 4? Yes!
- Path to q: [6, 2, 4]
Step 3: Compare path_p = [6, 2] and path_q = [6, 2, 4] element by element.
- Index 0: path_p[0] = 6, path_q[0] = 6 → match. LCA candidate = 6.
- Index 1: path_p[1] = 2, path_q[1] = 2 → match. LCA candidate = 2.
- Index 2: path_p has no more elements. Stop.
Step 4: The last matched node is 2, so LCA = 2.
Brute Force — Find Paths Then Compare — Watch how we trace paths from root to each target node, then compare the paths to find the last common node.
Algorithm
- Find the path from root to node
pusing DFS/BFS. Store the path in a list. - Find the path from root to node
qusing DFS/BFS. Store the path in a second list. - Compare both paths element by element from the start.
- The last node that matches in both paths is the LCA.
- Return the LCA node.
Code
class Solution {
public:
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
if (root == nullptr) return false;
path.push_back(root);
if (root == target) return true;
if (findPath(root->left, target, path) || findPath(root->right, target, path)) {
return true;
}
path.pop_back();
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pathP, pathQ;
findPath(root, p, pathP);
findPath(root, q, pathQ);
TreeNode* lca = root;
int minLen = min(pathP.size(), pathQ.size());
for (int i = 0; i < minLen; i++) {
if (pathP[i] == pathQ[i]) {
lca = pathP[i];
} else {
break;
}
}
return lca;
}
};class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def find_path(node, target, path):
if node is None:
return False
path.append(node)
if node == target:
return True
if find_path(node.left, target, path) or find_path(node.right, target, path):
return True
path.pop()
return False
path_p, path_q = [], []
find_path(root, p, path_p)
find_path(root, q, path_q)
lca = root
for i in range(min(len(path_p), len(path_q))):
if path_p[i] == path_q[i]:
lca = path_p[i]
else:
break
return lcaclass Solution {
private boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
if (root == null) return false;
path.add(root);
if (root == target) return true;
if (findPath(root.left, target, path) || findPath(root.right, target, path)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathP = new ArrayList<>();
List<TreeNode> pathQ = new ArrayList<>();
findPath(root, p, pathP);
findPath(root, q, pathQ);
TreeNode lca = root;
int minLen = Math.min(pathP.size(), pathQ.size());
for (int i = 0; i < minLen; i++) {
if (pathP.get(i) == pathQ.get(i)) {
lca = pathP.get(i);
} else {
break;
}
}
return lca;
}
}Complexity Analysis
Time Complexity: O(n)
In the worst case, finding the path from the root to a node requires visiting every node in the tree (think of a skewed tree). We do this twice (once for p and once for q), and then compare paths which takes at most O(h) where h is the height. Total: O(n) + O(n) + O(h) = O(n).
Space Complexity: O(n)
We store two paths, each of length at most h (the height of the tree). In the worst case (skewed tree), h = n, so both paths plus the recursion stack use O(n) space.
Why This Approach Is Not Efficient
The brute force approach treats the tree as a generic binary tree and completely ignores the BST ordering property. It traverses the tree twice to build two full paths, then compares them — using O(n) time and O(n) space.
The core inefficiency is that we do not leverage the BST property at all. In a BST, we can determine which subtree a value lies in by a single comparison with the current node's value. This means we can find the LCA in a single traversal without storing any paths.
The key insight: in a BST, if both p and q are smaller than the current node, the LCA must be in the left subtree. If both are larger, the LCA must be in the right subtree. The moment one target is on the left and the other is on the right (or one of them equals the current node), we have found the LCA. This eliminates the need for path storage entirely.
Better Approach - Recursive BST Traversal
Intuition
Now let's use the BST property to our advantage. In a BST, every node acts as a decision boundary: values less than the node go left, values greater go right.
Imagine you're standing at the root of the tree and holding two numbers (the values of p and q). You ask yourself:
- Are both numbers smaller than where I'm standing? Then both nodes must be to my left — go left.
- Are both numbers larger? Then both must be to my right — go right.
- One is smaller and one is larger (or one equals me)? Then I'm the split point — I am the LCA!
This is like finding a fork in a road. You walk down a single path, and the moment the two destinations require going in different directions, you've found the last common point.
Step-by-Step Explanation
Let's trace with the tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8:
Step 1: Start at root node 6. Compare p=2 and q=8 against current node 6.
- Is 2 < 6? Yes.
- Is 8 < 6? No.
- p and q are on different sides of 6 (one left, one right).
Step 2: Since p and q split at node 6, this node is the LCA.
- Return 6.
Let's also trace p = 2, q = 4:
Step 1: Start at root 6. Both p=2 and q=4 are less than 6.
- Both are in the left subtree. Recurse left.
Step 2: Now at node 2. Compare p=2 and q=4 against 2.
- Is 2 < 2? No.
- Is 4 < 2? No.
- p equals the current node, and q is to its right.
- They split here (one equals the node, one is in its subtree).
Step 3: Node 2 is the LCA. Return 2.
Recursive BST Traversal — Finding the Split Point — Watch how the BST property guides us directly to the LCA by comparing both target values against each node — no path storage needed.
Algorithm
- Start at the root of the BST.
- If both
p.valandq.valare less thanroot.val, recurse into the left subtree. - If both
p.valandq.valare greater thanroot.val, recurse into the right subtree. - Otherwise (one on each side, or one equals root), return the current root — it is the LCA.
Code
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return nullptr;
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 root is None:
return None
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 rootclass Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
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;
}
}Complexity Analysis
Time Complexity: O(h), where h is the height of the BST
We traverse at most one path from root to a leaf. In a balanced BST, h = log n, giving O(log n). In a skewed BST, h = n, giving O(n) worst case. On average for a reasonably balanced tree, this is O(log n).
Space Complexity: O(h)
The recursive call stack uses space proportional to the height of the tree. In a balanced tree this is O(log n), but in the worst case (skewed tree) it can be O(n).
Why This Approach Is Not Efficient
The recursive approach achieves O(h) time, which is already optimal in terms of the number of nodes visited. However, it uses O(h) space due to the recursion stack. In the worst case (a completely skewed BST with 10^5 nodes), this means O(n) = O(10^5) recursive calls, which could cause a stack overflow.
The insight for improvement: since we're always moving in one direction (left or right) at each step, this tail-recursive pattern can be trivially converted to an iterative loop, eliminating the recursion stack entirely and achieving O(1) space.
Optimal Approach - Iterative BST Traversal
Intuition
The iterative approach uses the exact same logic as the recursive one — compare both targets against the current node and decide to go left, go right, or stop — but replaces recursion with a simple while loop.
Think of it as walking down a corridor with signs at each junction. At each junction (node), the sign tells you: 'Both destinations are to the left', 'Both destinations are to the right', or 'Your destinations split here — this is the last common junction.' You just keep walking until you see the split sign. No need to remember where you came from (no stack), because you never need to go back.
Step-by-Step Explanation
Let's trace with the tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 0, q = 5:
Step 1: Start at root node 6.
- p=0 < 6 AND q=5 < 6. Both are less than 6.
- Move left to node 2.
Step 2: Now at node 2.
- p=0 < 2. q=5 > 2.
- p is on the left side, q is on the right side.
- They split at node 2.
Step 3: Node 2 is the LCA. Return 2.
The iterative version visited exactly 2 nodes and used no extra space beyond a single pointer variable.
Iterative BST Traversal — Walking to the Split Point — Watch the pointer walk down the tree using a simple while loop, comparing both targets at each node until it finds the split point — using O(1) extra space.
Algorithm
- Set
current = root. - While
currentis not null:
a. If bothp.valandq.valare less thancurrent.val, movecurrenttocurrent.left.
b. Else if bothp.valandq.valare greater thancurrent.val, movecurrenttocurrent.right.
c. Otherwise, returncurrent— it is the LCA (the targets split here, or one of them equalscurrent). - Return
current.
Code
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* current = root;
while (current != nullptr) {
if (p->val < current->val && q->val < current->val) {
current = current->left;
} else if (p->val > current->val && q->val > current->val) {
current = current->right;
} else {
return current;
}
}
return current;
}
};class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
current = root
while current:
if p.val < current.val and q.val < current.val:
current = current.left
elif p.val > current.val and q.val > current.val:
current = current.right
else:
return current
return currentclass Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode current = root;
while (current != null) {
if (p.val < current.val && q.val < current.val) {
current = current.left;
} else if (p.val > current.val && q.val > current.val) {
current = current.right;
} else {
return current;
}
}
return current;
}
}Complexity Analysis
Time Complexity: O(h), where h is the height of the BST
We traverse at most one root-to-leaf path. Each iteration does a constant-time comparison and moves one level deeper. In a balanced BST, h = log n, so the time is O(log n). In the worst case (skewed tree), h = n, giving O(n). Since we cannot avoid visiting at least the nodes on the path to the LCA, this is optimal.
Space Complexity: O(1)
We use only a single pointer variable (current) that walks down the tree. No recursion stack, no path arrays, no auxiliary data structures. This is the space-optimal solution.