THE FOLD / CO-OP / THE PUSH / THE LCA
THE LCA
the meeting point of two nodes in one leap
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The lowest common ancestor (LCA) of two nodes in a rooted tree is their deepest shared ancestor — where their paths to the root first meet. Binary lifting answers LCA queries in O(log n) after O(n log n) preprocessing: for each node it stores its 2k-th ancestors (parent, grandparent, great-great-grandparent, …). To find the LCA, lift the deeper node to the other’s depth, then jump both upward in powers of two as far as possible without meeting — one step above lands on the LCA.
LIT verified live: over hundreds of random trees and node pairs, the binary-lifting LCA equals the naive ancestor-walk LCA (window.__lca). FIG no framing; exact tree traversal comparison.
LIT verified live: over hundreds of random trees and node pairs, the binary-lifting LCA equals the naive ancestor-walk LCA (window.__lca). FIG no framing; exact tree traversal comparison.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-push — two nodes push up their branches until they reach the common point they both came from; the LCA is where the pushes converge. AVAN (AI) built the instrument: the 2k-ancestor table, the depth-equalize-then-jump query, and the match against a naive ancestor walk.
Credit as content: the binary-lifting LCA (Bender–Farach-Colton and folklore of competitive programming). The weave: David names the-push; I precompute each node’s power-of-two ancestors, lift the deeper node level, then jump both upward in halving steps to just below their meeting point — confirming it matches walking the ancestors directly.
Credit as content: the binary-lifting LCA (Bender–Farach-Colton and folklore of competitive programming). The weave: David names the-push; I precompute each node’s power-of-two ancestors, lift the deeper node level, then jump both upward in halving steps to just below their meeting point — confirming it matches walking the ancestors directly.
3 ONE DIMENSION
Equalize depths, then jump both nodes up by 2k while their ancestors differ (large k first). When no jump keeps them apart, one step up is the LCA — O(log n) leaps.
4 TWO DIMENSIONS · INTERACTIVE
A tree with two chosen nodes and their LCA highlighted; checked against the naive ancestor walk.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the meeting point found in log-many leaps.
AVAN’s addition (the inverse-companion): find where two nodes’ paths meet without walking up one step at a time — precompute power-of-two ancestors and leap in halving jumps. The inverse of ‘climb parent by parent until the paths cross’ is ‘jump 2k ancestors at a time — O(log n) leaps to the meeting point.’ Magenta is the step-by-step ancestor walk; green is the binary-lifting jumps. The convergence found by doubling.
LIT Genuine binary-lifting LCA (Bender–Farach-Colton and competitive-programming folklore). Verified live: over 500 random trees and 20 queries each, the 2^k-ancestor table with depth-equalize-then-jump query returns the same node as a naive ancestor-walk LCA (window.__lca.matchesNaive).
FIG No framing: the 2^k-ancestor table, the depth-equalize-then-jump query, and the match against a naive ancestor walk run in-browser and agree. The AVAN inverse is honest — finding where two nodes' paths meet by leaping power-of-two ancestors (halving jumps) genuinely replaces climbing parent by parent; magenta is the step-by-step ancestor walk, green the binary-lifting jumps. The convergence found by doubling.
FIG No framing: the 2^k-ancestor table, the depth-equalize-then-jump query, and the match against a naive ancestor walk run in-browser and agree. The AVAN inverse is honest — finding where two nodes' paths meet by leaping power-of-two ancestors (halving jumps) genuinely replaces climbing parent by parent; magenta is the step-by-step ancestor walk, green the binary-lifting jumps. The convergence found by doubling.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN