DSA · Patterns, not puzzles
How do you find the lowest common ancestor of two nodes?
Short answer
For a binary tree, recurse into both subtrees and return the node when the two targets are found on different sides. If both targets are not present, the problem needs a separate existence check.
The lowest common ancestor is the deepest node that has both targets in its subtree. In a general binary tree, the recursive solution returns a target when it sees one, and combines results from the left and right. The first node where both sides return non-null is the answer.
function lowestCommonAncestor(node, a, b) {
if (node === null || node === a || node === b) return node;
const left = lowestCommonAncestor(node.left, a, b);
const right = lowestCommonAncestor(node.right, a, b);
if (left !== null && right !== null) return node;
return left !== null ? left : right;
}The BST shortcut
If the tree is a binary search tree, you can use the ordering property without exploring both sides. Walk down from the root; the first node whose value lies between the two targets is the LCA.
function bstLca(root, a, b) {
let node = root;
while (node !== null) {
if (a < node.value && b < node.value) node = node.left;
else if (a > node.value && b > node.value) node = node.right;
else return node;
}
return null;
}Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1Why does the general binary tree solution work?
- 2How does the BST property simplify the problem?
- 3What changes if one node may not exist?
- 4How would you answer repeated LCA queries on the same tree?
Say it in the interview
In a general binary tree I recurse into both subtrees, and if one side returns a target and the other returns the other target, the current node is the lowest common ancestor. If the tree is a BST, I walk down using the ordering and stop at the first node between the two values. The general version assumes both nodes exist, so I mention that caveat.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.