Coding · Trees
Lowest Common Ancestor of a Binary Tree
- Reported in several places
- Medium
- E4 / L4
- 3 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
A binary tree is given in level-order form (null for a missing child) and all its values are different, and two values p and q are both in it. Return the value of the lowest node that has both p and q in its subtree, where a node counts as part of its own subtree. For example, with the tree [3,5,1,6,2,0,8,null,null,7,4], p = 6 and q = 4 give 5. The tree has up to 10,000 nodes.
Restated in our own words, not a quote from Meta or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: is it a plain binary tree or a search tree? (Plain, so ordering tricks do not apply.) Are the values unique? Are p and q guaranteed to be in the tree? Can p equal q? Can one be an ancestor of the other, and does a node count as its own ancestor? Are there parent pointers? How deep can the tree get?
Assumptions I would state: plain binary tree, unique values, both values present, a node is allowed to be its own ancestor (so if p is above q, the answer is p), no parent pointers, and the tree arrives as a level-order array, which I turn into nodes first.
Brute force
Say the obvious answer and why it is too slow.
The naive solution tests every node: for each one, search its subtree for p and for q, and keep the deepest node whose subtree contains both. It is easy to reason about and needs nothing but a basic search.
It repeats the same searches again and again. Each check costs O(size of the subtree), and on a chain of 10,000 nodes the subtree sizes are 10,000, 9,999, 9,998 and so on, around 50 million steps in total, so O(n²). A better middle step is to find the root-to-p path and the root-to-q path, each in O(n), and walk them together until they differ. That is O(n) time and O(h) space and is a perfectly good answer. The one-pass recursion below gets the same cost without building and comparing paths.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(h) call stack, h is the height
The pattern is tree recursion that combines the answers of the two children (a post-order). Write a function that returns what it found in a subtree: the node itself if it is p or q, otherwise whatever the left and right calls return, merged.
The rules are short. If the node is null, return null. If the node is p or q, return it at once, without looking further down. Otherwise search both children. If both searches return something, then p and q are in different child subtrees, so this node is the lowest one that has both: return it. If only one search returns something, pass that result up unchanged. If neither does, return null.
Why is it correct? A call returns non-null only if its subtree contains p or q. Take the lowest node that has both in its subtree. Both targets are in its subtree but not both in the same child, because otherwise a lower node would qualify. So either they sit in different children, which is the "both children reported" case, or one of them is the node itself. In the second case we return the node immediately when we reach it, and the other target is below it, so no other node ever sees two separate reports and the early return is correct. Nodes above the answer only ever receive one report and pass it up, so the answer reaches the root.
Out loud: "Each subtree reports whether it found p or q. The first node that hears from both sides is the answer." This relies on both values being in the tree. If q were missing, the code would return p as the answer.
Walk it through
A dry run on the example, step by step.
| Step | Node | Left result | Right result | Returns |
|---|---|---|---|---|
| 1 | 6 | - | - | 6 (is p) |
| 2 | 7 | null | null | null |
| 3 | 4 | - | - | 4 (is q) |
| 4 | 2 | null | 4 | 4 |
| 5 | 5 | 6 | 4 | 5 (both sides) |
| 6 | 0 | null | null | null |
| 7 | 8 | null | null | null |
| 8 | 1 | null | null | null |
| 9 | 3 | 5 | null | 5 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take the tree [3,5,1,6,2,0,8,null,null,7,4] with p = 6 and q = 4. The table lists nodes in the order their calls finish.
Node 6 is p, so it returns itself straight away. Node 7 has no children and is neither target, so it returns null. Node 4 is q and returns itself. Node 2 gets null from its left child (7) and 4 from its right, so it passes 4 up. Node 5 now gets 6 from its left and 4 from its right: both sides reported, so 5 is the answer and it returns itself. Nodes 0, 8 and 1 find nothing and return null. The root 3 hears 5 from the left and null from the right, so it passes 5 up. The final result is 5.
The code
Runnable JavaScript, checked against test cases.
function lowestCommonAncestor(values, p, q) {
if (values.length === 0 || values[0] === null) return null;
const found = findAncestor(buildTree(values), p, q);
return found === null ? null : found.val;
}
function findAncestor(node, p, q) {
if (node === null || node.val === p || node.val === q) return node;
const fromLeft = findAncestor(node.left, p, q);
const fromRight = findAncestor(node.right, p, q);
if (fromLeft !== null && fromRight !== null) return node;
return fromLeft !== null ? fromLeft : fromRight;
}
function buildTree(values) {
const root = { val: values[0], left: null, right: null };
const waiting = [root];
let next = 1;
for (let head = 0; head < waiting.length && next < values.length; head++) {
for (const side of ["left", "right"]) {
if (next >= values.length) break;
const value = values[next++];
if (value === null) continue;
waiting[head][side] = { val: value, left: null, right: null };
waiting.push(waiting[head][side]);
}
}
return root;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
p is an ancestor of q: the search stops at p and returns it, which is correct since a node counts as its own descendant.
- p equals q: the first match is returned, which is that node.
- Single node: the root is both values, and the answer is the root.
- Answer is the root: p and q are on different sides of it.
- Value 0 or negative values: the code compares node objects, never the truthiness of a value, so a value of 0 is safe.
- Very deep trees: recursion depth equals the height, which can be n for a chain. For huge chains use an iterative version with parent links.
- One target missing: not supported, and it would return the one that exists.
Follow-ups to expect
Where the interviewer pushes next.
- How does the answer get simpler if the tree is a binary search tree?
- How would you detect that p or q is missing from the tree?
- How would you answer thousands of such queries on the same tree quickly?
- What if every node has a parent pointer but you are not given the root?
- How would you rewrite it iteratively to avoid deep recursion?
Where candidates slip
The mistakes this problem punishes.
The classic slip is using the binary search tree shortcut, going left when both values are smaller and right when both are larger. That only works in a search tree, and this tree has no ordering.
- Returning null when only one side finds something, which throws away the found node.
- Ignoring the current node when it is p or q and looking only at its children, so a target that is an ancestor of the other is lost.
- Testing the truthiness of a value (so a value of 0 looks like "not found") instead of testing the node.
- Forgetting that a node is its own ancestor, and answering with its parent.
- Building the tree wrongly from the array.
- Doing a separate full search for p and q at every node, which is quadratic.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.