Lowest Common Ancestor of a Binary Search Tree
The briefingthe full drill, in my own words
The drill: Given two nodes somewhere in a binary search tree, find the deepest node that has both of them as descendants — a node counts as its own descendant.
A binary search tree arrives along with two of its nodes, and the task is to find the deepest node in the tree that counts both of them among its descendants.
A node is considered its own descendant, so if one of the two target nodes happens to be an ancestor of the other, that target node itself is the answer.
Both target nodes are guaranteed to exist somewhere in the tree, and the tree's search-tree ordering — everything smaller to the left, everything larger to the right — holds throughout.
- both target nodes exist in the tree and are distinct
- the tree can hold anywhere from a couple of nodes to a few thousand
- all values in the tree are unique and follow standard BST ordering
- a node counts as its own descendant when checking ancestry
The hintstake only what you need
HINT 1 THE NUDGE
Ignoring the search-tree ordering entirely still gives a correct answer: search both subtrees for each target and combine what comes back. It just never uses the one fact this tree offers for free.
HINT 2 THE STRUCTURE
In a BST, a node's value alone tells you which side any other value lives on. If both targets are smaller than the current node, the answer can't be here — it's entirely in the left subtree, and symmetrically for the right.
HINT 3 ONE STEP FROM THE ANSWER
Walk down from the root comparing both target values against the current node's value: same-side, step that way; split (or a match), stop — that node is the answer.
Coach's boardthe pattern, step by step
Find the deepest node that's an ancestor of both 3 and 5. The BST ordering tells us which side to walk without ever searching — start at the root, 6.
The splitstwo paces, two languages
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 curr
return Noneclass Solution:
def lowestCommonAncestor(self, root: "TreeNode", p: "TreeNode", q: "TreeNode") -> "TreeNode":
if root is None or root.val == p.val or root.val == q.val:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else rightclass 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) {
if (root == null || root.val == p.val || root.val == q.val) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED