Binary Search TreesProblem 7 of 22
Find LCA of 2 nodes in a BST
Problem Statement
Given a Binary Search Tree and two nodes, find the Lowest Common Ancestor (LCA) of the two nodes. The LCA of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).
Example:
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
LCA(2, 8) = 6
LCA(2, 4) = 2
LCA(3, 5) = 4
Approach 1: Brute Force (Find Paths and Compare)
Intuition
Find the path from root to each node, then find the last common node in both paths.
Algorithm
- Find path from root to node p
- Find path from root to node q
- Compare paths from the beginning
- Return the last common node before paths diverge
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class 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 (target.val < root.val) {
return findPath(root.left, target, path);
} else {
return findPath(root.right, target, path);
}
}
public TreeNode lowestCommonAncestorBruteForce(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 = null;
int i = 0;
while (i < pathP.size() && i < pathQ.size()) {
if (pathP.get(i) == pathQ.get(i)) {
lca = pathP.get(i);
} else {
break;
}
i++;
}
return lca;
}
}Complexity Analysis
- Time Complexity: O(n) - Two traversals to find paths
- Space Complexity: O(n) - Storing paths
Approach 2: Optimal (Using BST Property - Recursive)
Intuition
In a BST, we can determine the direction to traverse based on values:
- If both p and q are smaller than current node, LCA is in left subtree
- If both p and q are larger than current node, LCA is in right subtree
- Otherwise, current node is the LCA (paths split here)
Algorithm
- If both values are smaller than current, go left
- If both values are larger than current, go right
- Otherwise, current node is LCA
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
// Both nodes are in the left subtree
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
// Both nodes are in the right subtree
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
// Split point: one on left, one on right, or one is current
return root;
}
}Complexity Analysis
- Time Complexity: O(h) where h is height - O(log n) for balanced BST
- Space Complexity: O(h) - Recursion stack
Approach 3: Optimal (Iterative - Best Space)
Intuition
Same logic as recursive but using iteration to achieve O(1) space.
Algorithm
- Start from root
- If both values smaller, move left
- If both values larger, move right
- Otherwise, return current node
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode lowestCommonAncestorIterative(TreeNode root, TreeNode p, TreeNode q) {
TreeNode curr = root;
while (curr != null) {
if (p.val < curr.val && q.val < curr.val) {
// Both in left subtree
curr = curr.left;
} else if (p.val > curr.val && q.val > curr.val) {
// Both in right subtree
curr = curr.right;
} else {
// Found the split point (LCA)
return curr;
}
}
return null;
}
}Complexity Analysis
- Time Complexity: O(h) where h is height
- Space Complexity: O(1) - No extra space
Key Takeaways
- BST advantage: We can determine direction without searching both subtrees
- Split point: LCA is where paths to p and q diverge
- Iterative preferred: O(1) space vs O(h) for recursive
- Simpler than general tree LCA: No need to search entire tree
- This is LeetCode #235 - Lowest Common Ancestor of a BST
- Different from LeetCode #236 (LCA in binary tree) which requires searching both subtrees
- Edge case: One node can be ancestor of another