Where do two pieces of evidence meet?
Picture
The lowest common ancestor of two nodes is the deepest node whose subtree contains both, allowing a node to be its own ancestor. Each child can report whether it found relevant evidence. When the evidence arrives from both sides, the current node is where the two branches meet.
Predict
If one target is an ancestor of the other, must the answer be their parent’s node instead?
Reveal the reasoning
No. With the convention that a node is its own ancestor, that target is already their lowest common ancestor. State conventions before deriving base cases.
Go deeper: the return value can carry partial evidence
Use unique integer labels, and assume both target labels exist in the tree. A call returns the discovered target, an already found common ancestor, or None if neither target occurs in its subtree.
def common_ancestor(node, a, b):
if node is None:
return None
value, left, right = node
if value == a or value == b:
return value
left_result = common_ancestor(left, a, b)
right_result = common_ancestor(right, a, b)
if left_result is not None and right_result is not None:
return value
return left_result if left_result is not None else right_result
tree = (1, (2, (4, None, None), (5, None, None)), (3, None, None))
assert common_ancestor(tree, 4, 5) == 2
assert common_ancestor(tree, 4, 3) == 1
assert common_ancestor(tree, 2, 4) == 2
If both child returns contain evidence, the targets split across the current node. If only one does, both targets or the one partial finding lie on that side, so pass the result upward. Worst-case time is O(n) and stack space O(h).
On a BST with both keys present, ordering offers a shortcut: if both targets are smaller, go left; if both larger, go right; otherwise the current node separates them or equals a target. That takes O(h) time. On a general tree, using numeric comparisons this way would be invalid.
For many queries on one static tree, repeated full traversals may be wasteful. Parent/depth preprocessing and binary lifting are an extension once the one-query contract is understood.
Analogy limit: a partial finding is not proof that both requested targets exist. The existence assumption is doing real work in this compact implementation.
Change one rule
A target may be absent. Does this function now reliably return None when no valid LCA exists?
Check the variation
No. It may return the one present target. Verify target presence first, or return both a candidate and target-presence information from the traversal. Handle equal targets consistently with the chosen contract.
Connect
Diameter also detects where two useful branches meet. Tree DP formalizes richer child summaries when a single candidate is insufficient.