Lowest Common

Lowest Common Ancestor of a Binary Tree (LC 236): two marked nodes p and q, find the lowest node that has both below it — where a node counts as its own descendant. The piece runs the post-order pass one event at a time: enter a node, come back out of it, and when you come back out, hand something up. The thing to watch is that no node ever learns where it sits in the tree. It learns one fact from each child — did a target turn up on that side — and the whole algorithm is what it does with two facts.

Each node, once returned from, wears what its children told it: the left half of its ring lights blue when the left side found something, the right half when the right side did. One side lit means the node passes that find up, untouched — the blue arrow on the edge above it is the find travelling. Both halves lit is the answer, ringed amber: the paths from p and q join here, and the node knows it without ever having seen the root. The tag under every node is what it handed up — ∅ for nothing, ↑5 for a node.

Drag p onto an ancestor of q (the ancestor preset does it for you: p = 5, q = 4 on the brief’s tree) and the rule that looks like it should need a special case does not get one. The walk reaches 5, 5 is a target, 5 hands itself up without looking below — four nodes are drawn dashed and never entered — and everything else in the tree reports nothing, so 5 is what arrives at the root. The walk never found q. It did not have to: both targets are guaranteed to exist, and that guarantee is doing the work.

Three rules, switchable, because the second and third are what people write when they do not trust the first:

• stop at a target is the one-liner. Fewest visits; the skipped count is on screen.
• look below a target keeps going under a target and absorbs any find into the target itself. Every node visited, same answer — and the shape you need the moment existence is not guaranteed (LC 1644), because a walk that stops at p cannot know whether q is anywhere.
• split only is the trap: keep looking below a target, but only resolve a node when it sees one find on each side. It is right whenever p and q sit in different subtrees, and the moment one is an ancestor of the other it hands the wrong node to the root — the deeper target, in red, with the real answer ringed beside it.

Type any LeetCode level-order array into the tree box, or roll a random one.

Reuse

src/lowest-common.js is a framework-free ES module:

• treeFromLevelOrder(text) / toLevelOrder(tree) — LeetCode’s [3,5,1,6,2,0,8,null,null,7,4] form in and out. makeTree(n, { skew }) rolls a random tree. Trees are { nodes, root } with ids into nodes, each node carrying key, left, right, parent.
• lca(tree, p, q, variant) — the plain answer, in any of the three rules.
• trace(tree, p, q, { variant }) — one frame per enter / return event: { t, cur, value, from, path, report, visited, skipped, note }, where report maps every returned node to what each side told it and what it handed up. Also reports the ground truth (truth, from parent pointers — the LC 1650 shape), correct, and whether this is an ancestor case. Same trace-per-tick shape as thread, prune and rebase.
• simulate(tree, p, q) — all three variants over one instance.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

• split is deliberately wrong. It exists so the failure can be watched on the one input class that triggers it; do not reuse it as an answer.
• Keys must be distinct (LC’s constraint); the demo flags a tree box that repeats a key and keeps the last good tree. Targets that fall off the tree after an edit snap to nodes that exist.
• The demo bundles its own copy of lowest-common.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--preset=] [--rule=] [--at=] regenerates thumb.png through site/scripts/lib/chromium.mjs.