Lab 11 — LCA via Binary Lifting

Goal

Answer lowest-common-ancestor queries on a rooted tree in O(log n) after O(n log n) preprocessing: build the jump table up[k][v] = 2^k-th ancestor, then implement lca(u, v), kth_ancestor(v, k) (LC 1483 verbatim), and dist(u, v). Extend the table to path aggregates (max edge on path). Target: full class from cold start in <15 minutes.

Background Concepts

Jump table. up[0][v] = parent of v; up[k][v] = up[k−1][up[k−1][v]] — the 2^k-th ancestor is the 2^(k−1)-th ancestor of the 2^(k−1)-th ancestor. LOG = ⌈log₂ n⌉ rows, filled row by row after one BFS/DFS computes depth and parents. Any k-step walk decomposes into the binary expansion of k: ≤ LOG jumps.

LCA query. Lift the deeper node by depth[u] − depth[v] to equalize depths. If they now coincide, done. Otherwise lift both simultaneously, largest jumps first, taking a jump only when it does not land them on the same node — this keeps both strictly below the LCA; after all bits, both are children of the LCA.

Alternatives. Euler tour + sparse-table RMQ: LCA(u,v) = shallowest node in the Euler tour between the first occurrences of u and v — O(n log n) build, O(1) query via lab-04’s sparse table. Farach-Colton–Bender exploits that adjacent Euler depths differ by ±1 to reach O(n)/O(1). Offline: Tarjan’s algorithm answers all queries in one DFS with a DSU, O(n·α(n) + q). Binary lifting is the interview default: simplest to write, and it is the only one that also gives kth_ancestor and path aggregates for free.

Interview Context

LC 236 (LCA of a Binary Tree) is the toy: one query, O(n) recursion, everyone’s seen it. The real interview escalation is “now answer q = 2×10⁵ queries” — per-query O(n) walks become 4×10¹⁰ operations on an adversarial chain. Binary lifting is the expected answer at L5+; LC 1483 (Kth Ancestor of a Tree Node) is the canonical LeetCode instance and is exactly the jump table with no LCA logic at all. Path-aggregate variants (max edge between u and v) appear in system-flavored rounds via MST verification.

Problem Statement (LC 1483)

Given a tree of n nodes, node 0 as root, and parent[i] for each node, implement TreeAncestor(n, parent) with getKthAncestor(node, k) returning the k-th ancestor or −1. Generalized target: on the same tree, answer up to 2×10⁵ mixed queries lca(u, v) and dist(u, v).

Constraints

  • 1 ≤ n ≤ 2×10⁵ nodes; up to 2×10⁵ queries (LC 1483: 5×10⁴ each — same regime).
  • 0 ≤ k < n; tree given as parent array or adjacency list; static (no structural updates).
  • Recursion is a liability: a chain of 2×10⁵ overflows Python’s default stack.

Clarifying Questions

  1. Is the tree rooted? (Yes, at node 0; if unrooted, root it arbitrarily — LCA answers depend on the root.)
  2. One query or many? (Up to 2×10⁵ — preprocessing amortizes; for a single query, walk parents.)
  3. Weighted edges? (Unweighted here; for weighted dist, keep prefix sums root→v and use the same formula.)
  4. Static tree? (Yes. Insertions/deletions between queries need link-cut trees — out of scope.)
  5. Are u and v guaranteed valid, possibly equal? (Yes; lca(u, u) = u must hold.)

Examples

parent = [-1, 0, 0, 1, 1, 2, 2]          (perfect binary tree on 7 nodes)
kth_ancestor(3, 1) → 1     kth_ancestor(5, 2) → 0     kth_ancestor(6, 3) → -1
lca(3, 4) → 1              lca(3, 5) → 0              lca(1, 1) → 1
dist(3, 5) → 4             dist(0, 6) → 2

Initial Brute Force

Store only parent and depth. Per query: walk the deeper node up until depths match, then step both up in lockstep until they meet. kth_ancestor: k single steps.

Brute Force Complexity

O(depth) per query, O(n) worst case on a chain → O(n·q) = 4×10¹⁰ at n = q = 2×10⁵. Fine for one query (this is the right answer for LC 236); dead for many.

Optimization Path

Naive walk O(n)/query → binary lifting O(n log n) build, O(log n) query → Euler tour + sparse table O(n log n)/O(1) (lab-04) → Farach-Colton–Bender O(n)/O(1) → Tarjan offline O(n·α(n) + q). In interviews, lifting wins on code-length-to-power ratio; mention the O(1)-query reductions to show you know the landscape.

Final Expected Approach

from collections import deque

class LCA:
    """Binary lifting over a rooted tree. O(n log n) build, O(log n) query."""

    def __init__(self, n, adj, root=0):
        self.LOG = max(1, (n - 1).bit_length())
        self.depth = [0] * n
        up = [[-1] * n for _ in range(self.LOG)]
        seen = [False] * n
        seen[root] = True
        dq = deque([root])                       # iterative BFS: no recursion limit
        while dq:
            v = dq.popleft()
            for w in adj[v]:
                if not seen[w]:
                    seen[w] = True
                    up[0][w] = v
                    self.depth[w] = self.depth[v] + 1
                    dq.append(w)
        for k in range(1, self.LOG):             # up[k][v] = 2^k-th ancestor
            upk, prev = up[k], up[k - 1]
            for v in range(n):
                mid = prev[v]
                upk[v] = -1 if mid == -1 else prev[mid]   # guard: -1 wraps in Python!
        self.up = up

    def kth_ancestor(self, v, k):
        """Binary expansion of k. Returns -1 if the walk leaves the tree."""
        if k > self.depth[v]:
            return -1
        b = 0
        while k:
            if k & 1:
                v = self.up[b][v]
            k >>= 1
            b += 1
        return v

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        u = self.kth_ancestor(u, self.depth[u] - self.depth[v])  # equalize depths
        if u == v:
            return u
        for b in range(self.LOG - 1, -1, -1):    # descend: largest jumps first
            if self.up[b][u] != self.up[b][v]:
                u, v = self.up[b][u], self.up[b][v]
        return self.up[0][u]

    def dist(self, u, v):
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

Data Structures Used

  • up — LOG × n int table (the sparse “jump pointers”; ~n log n ints, the dominant memory cost).
  • depth — int array; BFS queue during build.
  • For path aggregates: a parallel mx[k][v] table of the max edge weight on each 2^k jump.

Correctness Argument

Table: by induction on k — up[k][v] composes two correct 2^(k−1) jumps, and 2^(k−1) + 2^(k−1) = 2^k. The −1 guard preserves “walked off the root” through compositions.

kth_ancestor: the depth check rejects k > depth(v); otherwise k ≤ depth(v) < 2^LOG, so every set bit of k has a table row, and the jumps compose to exactly k steps regardless of bit order (ancestor composition is associative).

lca: after equalization, u and v are at equal depth. Invariant of the descending loop: u ≠ v and both lie strictly below their LCA. A jump of 2^b is taken only when up[b][u] ≠ up[b][v] — two distinct nodes at equal depth cannot both be ancestors of anything shared, so the jump keeps both strictly below the LCA. Descending bit order is what makes the greedy exact: after considering bit b, the remaining distance to the LCA’s children is < 2^b (else the b-jump would have been taken). After bit 0, the distance is 0: both nodes are children of the LCA, and up[0][u] is the answer.

Complexity

OperationTimeSpace
Build (BFS + table)O(n log n)O(n log n)
kth_ancestor / lca / distO(log n)—
q queries totalO((n + q) log n)O(n log n)

Implementation Requirements

  • Iterative BFS/DFS only — a 2×10⁵ chain kills recursive DFS in Python and default-stack C++.
  • LOG = max(1, (n−1).bit_length()) — handles n = 1 and exact powers of two.
  • Explicit −1 guard when composing the table (Python’s list[-1] is the last element, not an error).
  • lca(u, u) == u and lca(root, v) == root must fall out without special-casing.
  • For LC 1483 submit only __init__ (from parent array) + getKthAncestor.

Tests

  • Fixed 7-node perfect binary tree — every pair hand-checkable (see Examples).
  • Chain of 2000: lca(n−1, n/2) == n/2, kth_ancestor(n−1, n−1) == 0, kth_ancestor(n−1, n) == −1, dist(0, n−1) == n−1.
  • Star: lca of any two leaves is the center.
  • n = 1: lca(0,0) == 0, kth_ancestor(0, 1) == −1.
  • Stress: 300 random trees (≤ 64 nodes), every query checked against parent-walking brute force and BFS distance. (All verified before this lab shipped.)
  • Perf: chain of 2×10⁵ + 2×10⁵ random queries — must finish in seconds, not minutes.

Follow-up Questions

  • Reduce LCA to RMQ and back. → Euler tour (2n−1 entries) turns LCA(u,v) into “index of minimum depth between first[u] and first[v]” — a lab-04 sparse table gives O(1) queries. Adjacent tour depths differ by ±1, which Farach-Colton–Bender exploits (√-sized blocks, precomputed in-block patterns) for true O(n)/O(1). The reduction also runs backwards: any RMQ instance becomes LCA on a Cartesian tree.
  • Max edge on the path u–v (MST verification / bottleneck routing)? → Augment: mx[k][v] = max edge on v’s 2^k jump, composed with max exactly as up composes. path_max(u,v) = max over the jumps both lifts take. An MST is optimal iff every non-tree edge (u,v,w) has w ≥ path_max(u,v). Works for any idempotent/associative aggregate (min, max, gcd, bitwise-or) — not sums under updates.
  • Why does lifting beat naive parent-walking? → Adversarial shape: a chain with queries pairing the two ends — naive is Θ(n) per query, Θ(nq) total; lifting caps every query at ⌈log₂ n⌉ ≈ 18 jumps. The table costs 18× the parent array in memory — the classic time/space trade.
  • Jump pointers on functional graphs? → LC 1483 never uses “tree-ness”: any graph where each node has exactly one out-edge (successor function) admits the same table. k-th successor, cycle entry detection, “where is chip x after 10⁹ steps” — all the same doubling. This is also how sparse tables on permutations work.
  • When is lifting not enough? → Path updates (“add w to every edge on u–v, then query”). The table is a baked snapshot; rebuilding is O(n log n) per update. Heavy-light decomposition (phase-12 lab-03) maps paths to O(log n) segment-tree ranges and handles updates in O(log² n). Rule of thumb: static path queries → lifting; dynamic → HLD.
  • Memory too tight at n = 10⁶? → Euler tour + sparse table stores the same O(n log n) but over 2n entries of the tour; the true fix is FCB O(n) or an ancestor-labeling scheme; or answer offline with Tarjan + DSU in O(n·α(n)).

Product Extension

Org-chart services answer “nearest common manager” and “reporting distance” for pairs of employees — exactly lca/dist with the CEO as root, precomputed nightly. File systems and DOM trees use LCA for “closest common container” (permission inheritance, event delegation). Network engineering: on a spanning tree of the topology, bottleneck bandwidth between two hosts is the path-min aggregate — the mx-table variant with min. Phylogenetics: LCA = most recent common ancestor, dist = evolutionary distance; biology databases precompute exactly this table.

Language/Runtime Follow-ups

  • Python: lay the table out as LOG lists of n ints (as above), not n lists of LOG — row-major matches the fill loop and halves cache misses; PyPy or sys.setrecursionlimit never fixes what iteration fixes for free.
  • C++: vector<array<int,18>> or a flat int up[LOG][N]; watch stack size if you insist on recursive DFS.
  • Java: int[][] up fine; beware ArrayDeque autoboxing — use int[] as an explicit stack.
  • Go: slices of slices are fine; BFS with an index pointer into a preallocated slice beats container/list.
  • JS/TS: Int32Array rows; recursion on 2×10⁵ chain overflows V8’s stack — iterate.

Common Bugs

  1. −1 wraparound: prev[-1] in Python silently reads the last node, corrupting the table with plausible-looking ancestors. Guard mid == -1 explicitly; in C++/Java the same bug is an index crash (kinder).
  2. Ascending bits in the LCA loop: the greedy “jump iff ancestors differ” is only exact largest-first; ascending order can strand the nodes short of the LCA. (kth_ancestor, by contrast, is order-independent.)
  3. Missing depth equalization: calling the bit loop on nodes of unequal depth returns a node that is an ancestor of neither.
  4. Returning before the u == v check: when one node is the ancestor of the other, equalization already lands on the LCA; falling through to up[0][u] returns its parent — off by one level.
  5. LOG off-by-one: n.bit_length() vs (n−1).bit_length() — for n an exact power of two the former wastes a row, the latter is tight; too small a LOG silently caps jumps and fails only on deep chains.
  6. Recursive DFS at n = 2×10⁵: RecursionError in Python, stack overflow elsewhere; always build iteratively.

Debugging Strategy

Build the table for an 8-node chain 0←1←…←7 and print it: row k must read “shift by 2^k, −1 past the root” (up[1][5] == 3, up[2][5] == 1, up[2][3] == -1). If any row disagrees, the composition loop or the −1 guard is wrong. Then trace lca(7, 4) by hand: equalize (7→4… depths 7 vs 4, lift 7 by 3 → node 4), equal → return 4. For a branching failure, print (b, u, v) per loop iteration — u and v must stay at equal depth and never coincide inside the loop; if they ever become equal mid-loop, bug 2 or 4.

Mastery Criteria

  • Wrote the full class (build + lca + kth_ancestor + dist) from cold start in <15 minutes.
  • Solved LC 1483 and LC 236 from cold start; stated why LC 236 alone does not need lifting.
  • Augmented the table with path-max on paper in <5 minutes and stated the MST-verification use.
  • Stated the Euler-tour RMQ reduction and the O(n)/O(1) name (Farach-Colton–Bender).
  • Explained descending-bit necessity in the LCA loop without prompting.
  • Named the boundary where lifting yields to HLD (path updates).