cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 49 of 218
Ideas this builds on
Trees49 / 218

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.