Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
Return the lowest common ancestor of two target values in an ordinary binary tree. The ancestor may be one of the targets itself. The course identifies targets by value and expects the returned object to be a node from the original tree. It is not a binary-search-tree problem, so value comparisons cannot choose a left or right search direction.
Let each subtree report a useful node
A recursive call returns null if its subtree contains neither target. If the current node matches either target, return that node. Otherwise search both children. If both searches return a non-null node, the targets have been found in different child subtrees, and the current node is their common ancestor.
If only one child returns a node, propagate it upward. That returned node may be a target still waiting to meet the other target, or it may already be the completed common ancestor. The parent does not need to distinguish those cases: without a result from its other side, it has no reason to replace that node.
Trace a split and an ancestor target
Consider root 10 with children 4 and 15, where 4 has children 2 and 7. Searching for 2 and 7 makes both child calls at node 4 return a match. Node 4 returns itself. At root 10, only the left call has a result, so 4 propagates to the final answer.
Searching for 4 and 7 returns 4 as soon as that node is reached. Under the promise that both targets exist, 4 is already a common ancestor because it contains itself and its descendant 7. The answer can therefore be a target node, even though its name includes the word ancestor.
State the presence and identity promises
This compact recursion assumes the two requested values exist and identify the intended nodes unambiguously. If one is absent, it may return the other target rather than signal that a pair was never found. Supporting absent targets requires additional presence information, such as a count of discovered targets or a separate validation step.
Return the original node, not a freshly allocated object containing the same data. The runner's BinaryNodeRef contract checks that relationship before reporting the data value. A value-only test can otherwise accept a fabricated node and miss an identity error. Duplicate target values require node references or another unique identifier to remove ambiguity.
Why the first split is the lowest ancestor
When both child subtrees return matches, no descendant confined to one of those subtrees can contain both targets. The current node is therefore the lowest node that contains them together. Once that result propagates upward, higher ancestors cannot improve it, and the algorithm keeps the lower result.
If a current node is itself a target, no proper descendant can be an ancestor of that node, so returning it is also lowest whenever the other target lies beneath it. These two cases cover a split across children and a target on the ancestor path. Null leaves supply the no-match base case.
Costs and revealing tests
The traversal visits at most n nodes and takes O(n) time. Its recursive stack uses O(h) space for tree height h, with O(n) worst-case depth on a chain. No parent map or sorted ordering is required. Very deep trees can motivate an iterative parent-map solution at the cost of O(n) auxiliary storage.
Test targets on opposite sides of the root, targets in one small subtree, a target that is the ancestor, reversed target argument order, and a skewed tree. Build an independent oracle by finding each target's root path and taking their final shared node. For a follow-up with many repeated queries on one fixed tree, discuss preprocessing rather than repeating a complete traversal for every pair.
Continue with the implementation
Read the JavaScript walkthrough for the current code and links to the other programming languages. Use the original lesson for practice.