Lowest Common Ancestor & Binary Lifting

The previous lessons gave us a rooted tree and a single root-to-node path for each vertex. Many problems instead concern two vertices at once: the distance between $u$ and $v$, the highest fork their paths share, the smallest region containing two nested regions. Each reduces to the lowest common ancestor.

The LCA is well defined and unique: the sets of ancestors of $u$ and of $v$ are each a chain from the root, so their intersection is a chain, and a finite chain has a unique deepest element.

from __future__ import annotations

from collections.abc import Hashable, Iterable
from typing import Generic, Optional, TypeVar

Label = TypeVar("Label", bound=Hashable)

class TreeNode(Generic[Label]):
  """
    One tree node: its label, its parent (None only at the root), its\n
    depth below the root, and the list of its child nodes.\n
  """

  def __init__(self, label: Label) -> None:
    self.label: Label = label
    self.parent: Optional[TreeNode[Label]] = None
    self.depth: int = 0
    self.children: list[TreeNode[Label]] = []

  def __repr__(self) -> str:
    return f"TreeNode({self.label!r}, depth={self.depth})"

class RootedTree(Generic[Label]):
  """
    A tree rooted at a fixed node, with parent pointers and depths filled.\n
    Pass the root label, then `add_edge(parent, child)` for each tree edge\n
    (in any order); calling `finalize()` runs one DFS from the root to set\n
    every node's parent and depth.\n
  """

  def __init__(self, root_label: Label) -> None:
    self.root_label: Label = root_label
    self._nodes: dict[Label, TreeNode[Label]] = {}
    # adjacency of undirected tree edges, resolved to a rooting by DFS.
    self._adjacency: dict[Label, list[Label]] = {}
    self._node(root_label)

  def _node(self, label: Label) -> TreeNode[Label]:
    """
      The node for `label`, creating it (and its adjacency slot) if absent.\n
    """
    node = self._nodes.get(label)
    if node is None:
      node = TreeNode(label)
      self._nodes[label] = node
      self._adjacency[label] = []
    return node

  def add_edge(self, parent_label: Label, child_label: Label) -> None:
    """
      Record a tree edge between two labels (creating either node).\n
      Orientation is fixed later by the DFS from the root, so the order\n
      of the endpoints here does not matter.\n
    """
    self._node(parent_label)
    self._node(child_label)
    self._adjacency[parent_label].append(child_label)
    self._adjacency[child_label].append(parent_label)

  def finalize(self) -> RootedTree[Label]:
    """
      Root the tree at `root_label`: DFS the edges to set each node's\n
      parent, depth, and child list. Returns self for chaining.\n
    """
    root: TreeNode[Label] = self._nodes[self.root_label]
    root.parent = None
    root.depth = 0
    root.children = []

    # iterative DFS keeps deep / degenerate trees off the call stack.
    stack: list[TreeNode[Label]] = [root]
    visited: set[Label] = {self.root_label}
    while stack:
      current: TreeNode[Label] = stack.pop()
      current.children = []

      # adopt each unseen neighbor as a child, one depth below.
      for neighbor_label in self._adjacency[current.label]:
        if neighbor_label in visited:
          continue
        visited.add(neighbor_label)

        child: TreeNode[Label] = self._nodes[neighbor_label]
        child.parent = current
        child.depth = current.depth + 1
        current.children.append(child)
        stack.append(child)
    return self

  def node(self, label: Label) -> TreeNode[Label]:
    """
      The node carrying `label` (raises KeyError if absent).\n
    """
    return self._nodes[label]

  def parent_of(self, label: Label) -> Optional[Label]:
    """
      The label of `label`'s parent, or None at the root.\n
    """
    parent: Optional[TreeNode[Label]] = self._nodes[label].parent
    return None if parent is None else parent.label

  def depth_of(self, label: Label) -> int:
    """
      The depth of `label` below the root (the root is depth 0).\n
    """
    return self._nodes[label].depth

  @property
  def labels(self) -> list[Label]:
    """
      Every node label, in insertion order.\n
    """
    return list(self._nodes)

  def __contains__(self, label: Label) -> bool:
    return label in self._nodes

  def __len__(self) -> int:
    return len(self._nodes)

def tree_from_edges(
  root_label: Label,
  edges: Iterable[tuple[Label, Label]],
) -> RootedTree[Label]:
  """
    Build and finalize a RootedTree from a root label and an iterable of\n
    undirected `(label, label)` tree edges — a convenience for callers and\n
    tests that already hold the edge list.\n
  """
  tree: RootedTree[Label] = RootedTree(root_label)
  for first_label, second_label in edges:
    tree.add_edge(first_label, second_label)
  return tree.finalize()

The naive walk

If every node stores a parent pointer and a depth, one query is easy. Lift the deeper of $u,v$ until both sit at the same depth, then advance both pointers up in lockstep; the first node they agree on is the LCA.

This needs no preprocessing and is correct, but each step moves up one edge, so a query costs $O(h)$ where $h$ is the tree's height. On a balanced tree $h=O(\log n)$, but on a degenerate path $h=\Theta (n)$, and $q$ queries cost $O(qn)$. We want a query cost that does not depend on shape. (For the asymptotic notation, see asymptotic analysis.)

from collections.abc import Hashable
from typing import TypeVar

from rooted_tree import RootedTree, TreeNode

Label = TypeVar("Label", bound=Hashable)

def naive_lca(
  tree: RootedTree[Label],
  first_label: Label,
  second_label: Label,
) -> Label:
  """
    The lowest common ancestor of two labels by the unprocessed walk.\n
    Lifts the deeper node to equal depth, then climbs both together until\n
    they meet. Runs in O(height) time and needs no preprocessing.\n
  """
  first: TreeNode[Label] = tree.node(first_label)
  second: TreeNode[Label] = tree.node(second_label)

  # bring the deeper node up so both sit at the same depth.
  while first.depth > second.depth:
    assert first.parent is not None
    first = first.parent
  while second.depth > first.depth:
    assert second.parent is not None
    second = second.parent

  # now climb in lockstep; equal depth keeps the meeting point the LCA.
  while first is not second:
    assert first.parent is not None and second.parent is not None
    first = first.parent
    second = second.parent
  return first.label

Binary lifting

To address this, make each jump cover an exponentially larger distance. Instead of go up one, precompute, for every node $v$ and every $k$, a pointer that goes up $2^k$ edges at once.

The whole table is built from a single doubling identity: climbing $2^k$ edges is climbing $2^{k-1}$ edges twice.

So column $k$ of the table is computed entirely from column $k-1$, one pass per power of two. The number of columns is $K=\lceil {\log }_{2}n\rceil$, since no node has an ancestor more than $n-1$ edges up.

The table has $n(K+1)$ entries and each costs $O(1)$, so preprocessing is $O(n\log n)$ time and $O(n\log n)$ space.

$k$-th ancestor in $O(\log n)$

Any non-negative integer $k$ has a unique binary expansion, so the climb of $k$ edges decomposes into jumps of size $2^0,2^1,2^2,\dots$, one jump per set bit. Take each set bit from low to high and follow the matching column of up.

At most $K+1$ bits are set, so this is $O(\log n)$. The order of the jumps does not matter for the destination (they compose to the same total climb), but processing low bits first keeps the running node well-defined at each step.

LCA in $O(\log n)$

The LCA query reuses the same jumps as two phases. Phase 1 lifts the deeper node up by exactly $depth[u]-depth[v]$, a single $\text{Kth-Ancestor}$ call, so $u$ and $v$ sit at equal depth. If they now coincide, one was an ancestor of the other and we are done. Phase 2 lifts both nodes simultaneously: scanning $k$ from high to low, we jump both up by $2^k$ only when that keeps them distinct. When the loop ends, $u$ and $v$ are the two distinct children-side nodes just below the LCA, so the answer is their common parent.

The depth-equalizing jump is $O(\log n)$ and the second loop runs $K+1$ times, so each LCA query is $O(\log n)$ after the one-time $O(n\log n)$ build.

Here $u$ and $v$ already share depth; both lift to $c$ and $b$ (kept distinct), then one parent step lands on $a=\mathrm{lca}(u,v)$, drawn in acc.

A worked example

The whole method lives in the up grid, so we build one in full. Root the twelve-node tree below at node $1$; depths run from $0$ at the root to $5$ at node $11$.

With $n=12$ we get $K=\lceil {\log }_{2}12\rceil =4$, but the deepest node sits only $5$ edges from the root and $2^3=8>5$, so columns $0$ through $3$ already saturate: column $4$ would repeat column $3$ exactly (every $8$-jump already lands on the root). We show columns $\mathrm{0..3}$. Rows are nodes, columns are $k$, each entry is the $2^k$-th ancestor, and the root's pointers stay at the root itself.

The build fills this grid one column at a time, left to right, and every entry is two array reads. Row $11$ shows the doubling in action:

• $up[11][0]=parent[11]=9$ (from the DFS);
• $up[11][1]=up[up[11][0]][0]=up[9][0]=7$: two $1$-jumps make a $2$-jump;
• $up[11][2]=up[up[11][1]][1]=up[7][1]=2$: two $2$-jumps make a $4$-jump;
• $up[11][3]=up[up[11][2]][2]=up[2][2]=1$ — and $11$'s $8$th ancestor clamps to the root, since $11$ is only $5$ deep.

No entry ever looks at the tree again; column $k$ reads only column $k-1$.

A $k$-th-ancestor query, bit by bit

Find the $5$th ancestor of node $11$. Write $5=101_2$: bits $0$ and $2$ are set, bit $1$ is clear. $\text{Kth-Ancestor}$ scans the bits low to high:

• bit $0$ set: $v\leftarrow up[11][0]=9$: climbed $1$ edge, $4$ to go;
• bit $1$ clear: skip column $1$;
• bit $2$ set: $v\leftarrow up[9][2]=1$: climbed $4$ more edges.

Answer: node $1$. That checks out: $depth[11]=5$, so its $5$th ancestor is exactly the root. The two table cells touched are the ones highlighted in acc above: two reads answered a $5$-edge climb.

An LCA query, phase by phase

Now run $\text{LCA}(11,12)$ in full. Depths are $5$ and $4$, so $u=11$ is deeper.

Phase 1 (equalize). Lift $11$ by $depth[11]-depth[12]=1=1_2$: one $k=0$ jump, $u\leftarrow up[11][0]=9$. Both nodes now sit at depth $4$. They differ ($9\ne 12$), so the LCA is strictly above and phase 2 runs.

Phase 2 (simultaneous lift). Scan $k=3$ down to $0$, jumping both nodes only when their $2^k$-th ancestors differ:

• $k=3$: $up[9][3]=1$ and $up[12][3]=1$: equal, so an $8$-jump would overshoot the LCA; skip.
• $k=2$: $up[9][2]=1$ and $up[12][2]=1$: equal again ($4$-jumps from depth $4$ also land on the root); skip.
• $k=1$: $up[9][1]=4$ and $up[12][1]=6$ — different, safe to jump: $u\leftarrow 4$, $v\leftarrow 6$, both now at depth $2$.
• $k=0$: $up[4][0]=2$ and $up[6][0]=3$ — different again: $u\leftarrow 2$, $v\leftarrow 3$, depth $1$.

The loop ends with $u=2$ and $v=3$, the two children of the LCA, and the algorithm returns $up[2][0]=1$. Correct: nodes $11$ and $12$ hang from different subtrees of the root, so $\mathrm{lca}(11,12)=1$.

The two skipped levels follow from the greedy construction. From depth $4$ the LCA sits $d=4$ edges up on each side, so the loop must climb exactly $d-1=3$ edges before the final parent step, and $3=11_2$ selects the $k=1$ and $k=0$ jumps while rejecting $k=3$ and $k=2$ as overshoots — the binary expansion of $d-1$, computed without ever knowing $d$.

The costs, exactly

The preprocessing and query bounds come from counting table reads.

• Build. The DFS fills $parent$ and $depth$ in $O(n)$. The table has $n(K+1)$ entries with $K=\lceil {\log }_{2}n\rceil$, each computed by one composition, so the build does $n(K+1)=n\lceil {\log }_{2}n\rceil +n$ constant-time steps: $\Theta (n\log n)$ time, and the same in space since the table persists.
• $k$-th ancestor. One jump per set bit of $k$, at most $K+1=\lceil {\log }_{2}n\rceil +1$ jumps, each one array read: $O(\log n)$.
• LCA. Phase 1 is one $k$-th-ancestor call ($\le K+1$ reads). Phase 2 tests every level once — exactly $K+1$ comparisons, each two reads, with at most $K+1$ jumps taken — then one final read. In total at most $3(K+1)+1\approx 3{\log }_{2}n$ table reads per query.

Concretely, at $n=10^6$: $K=20$, the table holds $2.1\times 10^7$ entries (about $84$ MB at $4$ bytes each), and a query costs at most $\sim 63$ array reads — against up to $10^6$ pointer steps for the naive walk on a path-shaped tree. The method trades memory for query time, and on large inputs memory is the binding constraint.

Application: tree distance and path queries

LCA turns a two-vertex path question into arithmetic on depths. The unique path from $u$ to $v$ in a tree goes up from $u$ to $\mathrm{lca}(u,v)$ and back down to $v$, so its length is

On the worked tree, $\mathrm{dist}(11,12)=5+4-2\cdot 0=9$, and counting edges along $11-9-7-4-2-1-3-6-10-12$ confirms it: nine edges.

Each query is one LCA plus $O(1)$ work, hence $O(\log n)$. The same decomposition answers is $w$ on the $u-v$ path?, aggregates a value along the path (split into the two vertical legs), or, combined with $\text{Kth-Ancestor}$, emits step-by-step U/L/R directions: climb $depth[u]-depth[\text{lca}]$ steps up, then walk the recorded downward path to $v$.

from __future__ import annotations

from collections.abc import Hashable
from typing import Generic, Optional, TypeVar

from rooted_tree import RootedTree, TreeNode

Label = TypeVar("Label", bound=Hashable)

class BinaryLifting(Generic[Label]):
  """
    Preprocessed 2^k-th-ancestor table over a rooted tree.\n
    Building it costs O(n log n) time and space; afterward each\n
    k-th-ancestor, LCA, and distance query runs in O(log n).\n
  """

  def __init__(self, tree: RootedTree[Label]) -> None:
    self._tree: RootedTree[Label] = tree
    self._depth: dict[Label, int] = {
      label: tree.depth_of(label) for label in tree.labels
    }

    # number of columns: no node climbs more than n - 1 edges up.
    self._max_power: int = max(1, (len(tree) - 1).bit_length())

    # ancestors[label][k] is the 2^k-th ancestor, or None past the root.
    self._ancestors: dict[Label, list[Optional[Label]]] = {}
    self._build()

  def _build(self) -> None:
    """
      Fill the doubling table column by column.\n
      Column 0 is the parent; column k composes column k-1 with itself.\n
    """
    # column 0: direct parents (None at the root).
    for label in self._tree.labels:
      self._ancestors[label] = [self._tree.parent_of(label)]

    # column k: the 2^(k-1)-th ancestor of the 2^(k-1)-th ancestor.
    for power in range(1, self._max_power + 1):
      for label in self._tree.labels:
        midpoint: Optional[Label] = self._ancestors[label][power - 1]
        if midpoint is None:
          self._ancestors[label].append(None)
        else:
          self._ancestors[label].append(self._ancestors[midpoint][power - 1])

  def kth_ancestor(self, label: Label, steps: int) -> Optional[Label]:
    """
      The ancestor `steps` edges above `label`, or None if that climbs\n
      past the root. Decomposes the climb by the set bits of `steps`,\n
      following one column of the table per bit — O(log n).\n
    """
    if steps < 0:
      raise ValueError("steps must be non-negative")

    current: Optional[Label] = label
    bit: int = 0

    # follow the column for each set bit of `steps`, low bit first.
    while steps > 0:
      if current is None:
        return None
      if steps & 1:
        current = self._ancestors[current][bit]
      steps >>= 1
      bit += 1
    return current

  def lca(self, first_label: Label, second_label: Label) -> Label:
    """
      The lowest common ancestor of two labels in O(log n).\n
      Phase 1 lifts the deeper node to equal depth; phase 2 jumps both up\n
      by decreasing powers of two whenever that keeps them distinct, so\n
      they land on the LCA's two children and the answer is their parent.\n
    """
    first: Label = first_label
    second: Label = second_label

    # phase 1: equalize depth by a single k-th-ancestor climb.
    if self._depth[first] < self._depth[second]:
      first, second = second, first
    lifted: Optional[Label] = self.kth_ancestor(
      first, self._depth[first] - self._depth[second]
    )

    # if the deeper node was an ancestor of the other, it is the LCA.
    assert lifted is not None
    first = lifted
    if first == second:
      return first

    # phase 2: jump both up greedily, high power to low, while distinct.
    for power in range(self._max_power, -1, -1):
      first_up: Optional[Label] = self._ancestors[first][power]
      second_up: Optional[Label] = self._ancestors[second][power]
      if first_up != second_up:
        assert first_up is not None and second_up is not None
        first, second = first_up, second_up

    # both now sit just below the LCA; their common parent is the answer.
    parent: Optional[Label] = self._ancestors[first][0]
    assert parent is not None
    return parent

  def distance(self, first_label: Label, second_label: Label) -> int:
    """
      The number of edges on the unique path between two labels.\n
      The path climbs to the LCA and back down, so its length is\n
      depth[first] + depth[second] - 2 * depth[lca].\n
    """
    ancestor: Label = self.lca(first_label, second_label)
    return (
      self._depth[first_label]
      + self._depth[second_label]
      - 2 * self._depth[ancestor]
    )

def directions(
  lifting: BinaryLifting[Label],
  tree: RootedTree[Label],
  source_label: Label,
  target_label: Label,
) -> str:
  """
    Step-by-step moves from `source` to `target` in a binary tree, where\n
    each node's first child is `L` and its second is `R`. The path climbs\n
    `U` from the source to the LCA, then descends the recorded child slots\n
    down to the target. Returns the move string (empty when they coincide).\n
  """
  ancestor: Label = lifting.lca(source_label, target_label)

  # the upward leg: one 'U' per edge from the source to the LCA.
  ups: str = "U" * (tree.depth_of(source_label) - tree.depth_of(ancestor))

  # the downward leg: walk target up to the LCA, recording child slots.
  downs: list[str] = []
  node: TreeNode[Label] = tree.node(target_label)
  ancestor_node: TreeNode[Label] = tree.node(ancestor)

  # each edge is 'L' or 'R' by which child slot the node occupies.
  while node is not ancestor_node:
    parent: Optional[TreeNode[Label]] = node.parent
    assert parent is not None
    slot: int = parent.children.index(node)
    downs.append("L" if slot == 0 else "R")
    node = parent

  # slots were collected bottom-up, so reverse for the top-down path.
  downs.reverse()
  return ups + "".join(downs)

Alternatives

Binary lifting is the most broadly useful LCA method, but two alternatives beat it on specific query models.¹

• Euler tour + sparse-table RMQ. Record the Euler traversal of the tree (each node appended on entry and after each child returns); within it, the LCA of $u$ and $v$ is the shallowest node visited between any occurrence of $u$ and of $v$. That reduces LCA to a range-minimum query over the depth array, which a sparse table answers in $O(1)$ after an $O(n\log n)$ build.² So queries drop to $O(1)$, but the structure is static and does not directly give $k$-th ancestors.
  The reduction is best seen laid out. Below the tree, the Euler tour writes each node as it is entered and re-entered, with its depth underneath. The LCA of $u$ and $v$ is the shallowest entry anywhere between an occurrence of $u$ and one of $v$ — i.e. the minimum of that depth subarray (shaded), which here is $a$:

The $O(1)$ query comes from covering the range with two overlapping blocks. Precompute, for every index $i$ and power $j$, the minimum of the length-$2^j$ block starting at $i$ ($O(n\log n)$ entries, each from two smaller blocks). A query range of length $\ell$ is then covered by two overlapping blocks of length $2^{\lfloor {\log }_2\ell \rfloor }$, one flush left and one flush right; minimum is idempotent, so the overlap does no harm, and the answer is the smaller of two precomputed values. On a six-node tree ($1$ has children $2,3$; node $2$ has children $4,5$; node $3$ has child $6$) the tour has $2\cdot 6-1=11$ entries, and the query $\mathrm{lca}(4,6)$ spans tour indices $2$ through $8$ — length $7$, block length $2^{\lfloor {\log }_{2}7\rfloor }=4$:

Block $L$ covers indices $\mathrm{2..5}$ with depth minimum $1$; block $R$ covers $\mathrm{5..8}$ with depth minimum $0$. The smaller is $0$, at index $6$, so the LCA is node $1$ — found with two lookups and one comparison, whatever the size of the tree.

• Tarjan's offline LCA. If all query pairs are known in advance, a single DFS with a union-find structure answers them in near-linear $O((n+q)\alpha )$ total time, processing each query when its second endpoint is first reached.³

from collections.abc import Hashable
from typing import Generic, TypeVar

from rooted_tree import RootedTree, TreeNode

Label = TypeVar("Label", bound=Hashable)

class SparseTable:
  """
    A static sparse table for range-minimum over (depth, index) pairs.\n
    Each level doubles the window: levels[k][i] is the argmin over the\n
    block of length 2^k starting at i. A query covers any range with two\n
    overlapping power-of-two blocks, so it is O(1) after an O(n log n) build.\n
  """

  def __init__(self, values: list[tuple[int, int]]) -> None:
    self._values: list[tuple[int, int]] = values
    length: int = len(values)

    # log_floor[span] = floor(log2(span)) for span from 1 to length.
    self._log_floor: list[int] = [0 for _ in range(length + 1)]
    for span in range(2, length + 1):
      self._log_floor[span] = self._log_floor[span // 2] + 1

    # levels[0] is the identity; each later level merges two half-blocks.
    self._levels: list[list[int]] = [list(range(length))]
    power: int = 1
    while power * 2 <= length:
      previous: list[int] = self._levels[-1]
      merged: list[int] = []
      for start in range(length - power * 2 + 1):
        left: int = previous[start]
        right: int = previous[start + power]
        merged.append(left if values[left] <= values[right] else right)
      self._levels.append(merged)
      power *= 2

  def argmin(self, low: int, high: int) -> int:
    """
      The index of the minimum value over the inclusive range [low, high].\n
    """
    level: int = self._log_floor[high - low + 1]
    block: int = 1 << level
    left: int = self._levels[level][low]
    right: int = self._levels[level][high - block + 1]
    return left if self._values[left] <= self._values[right] else right

class EulerTourLCA(Generic[Label]):
  """
    Preprocessed Euler-tour + RMQ structure answering LCA in O(1).\n
    Building the tour and its sparse table costs O(n log n); each query is\n
    a single range-minimum over the depth array between the two nodes.\n
  """

  def __init__(self, tree: RootedTree[Label]) -> None:
    # the Euler tour: labels in visit order, with their depths alongside.
    self._tour_labels: list[Label] = []
    depths: list[int] = []

    # first occurrence of each label in the tour pins its query range.
    self._first_seen: dict[Label, int] = {}

    self._build_tour(tree, depths)

    # pair each tour position with its depth and index for a stable argmin.
    keyed: list[tuple[int, int]] = [
      (depth, position) for position, depth in enumerate(depths)
    ]
    self._table: SparseTable = SparseTable(keyed)

  def _build_tour(self, tree: RootedTree[Label], depths: list[int]) -> None:
    """
      Walk the tree, appending each node on entry and after every child\n
      returns, recording depths and first occurrences as we go.\n
    """
    root: TreeNode[Label] = tree.node(tree.root_label)

    # iterative Euler walk; each frame is (node, next-child-index).
    stack: list[tuple[TreeNode[Label], int]] = [(root, 0)]
    while stack:
      node, child_index = stack[-1]

      # on first arrival, append the node and pin its first occurrence.
      if child_index == 0:
        self._first_seen.setdefault(node.label, len(self._tour_labels))
        self._tour_labels.append(node.label)
        depths.append(node.depth)
      # advance this frame, then descend into the next child.
      if child_index < len(node.children):
        stack[-1] = (node, child_index + 1)
        child: TreeNode[Label] = node.children[child_index]
        stack.append((child, 0))

      # child returned: re-record the parent (the Euler re-entry).
      else:
        stack.pop()
        if stack:
          parent_node, _ = stack[-1]
          self._tour_labels.append(parent_node.label)
          depths.append(parent_node.depth)

  def lca(self, first_label: Label, second_label: Label) -> Label:
    """
      The lowest common ancestor of two labels in O(1).\n
      It is the shallowest node anywhere between their first occurrences\n
      in the Euler tour — one range-minimum query over the depth array.\n
    """
    low: int = self._first_seen[first_label]
    high: int = self._first_seen[second_label]
    if low > high:
      low, high = high, low
    return self._tour_labels[self._table.argmin(low, high)]

from collections.abc import Hashable, Iterable
from typing import TypeVar

from rooted_tree import RootedTree, TreeNode
from union_find import UnionFind

Label = TypeVar("Label", bound=Hashable)

WHITE: int = 0  # not yet visited
GRAY: int = 1  # in progress, descendants still being explored
BLACK: int = 2  # finished, unioned into its parent

def tarjan_offline_lca(
  tree: RootedTree[Label],
  queries: Iterable[tuple[Label, Label]],
) -> list[Label]:
  """
    The LCA of each pair in `queries`, returned in the same order.\n
    One DFS over the tree with a union-find: a query is answered when its\n
    second endpoint is first reached, as the representative of the other.\n
  """
  query_list: list[tuple[Label, Label]] = list(queries)

  # for each node, the indices of queries touching it, with the partner.
  pending: dict[Label, list[tuple[Label, int]]] = {
    label: [] for label in tree.labels
  }

  # register each query on both of its endpoints.
  for index, (first_label, second_label) in enumerate(query_list):
    pending[first_label].append((second_label, index))
    pending[second_label].append((first_label, index))

  components: UnionFind[Label] = UnionFind(tree.labels)

  # the current representative (highest finished ancestor) of each set.
  representative: dict[Label, Label] = {
    label: label for label in tree.labels
  }
  color: dict[Label, int] = {label: WHITE for label in tree.labels}

  # seed answers with each pair's first endpoint; overwritten as resolved.
  answers: list[Label] = [first_label for first_label, _ in query_list]

  # explicit stack of (node, next-child-index) to keep deep trees safe.
  root: TreeNode[Label] = tree.node(tree.root_label)
  stack: list[tuple[TreeNode[Label], int]] = [(root, 0)]
  color[root.label] = GRAY
  while stack:
    node, child_index = stack[-1]

    # descend into the next unexplored child, marking it gray.
    if child_index < len(node.children):
      stack[-1] = (node, child_index + 1)
      child: TreeNode[Label] = node.children[child_index]
      color[child.label] = GRAY
      stack.append((child, 0))
    else:
      # node is finished; settle any query whose partner is already black.
      stack.pop()
      color[node.label] = BLACK
      for partner_label, index in pending[node.label]:
        if color[partner_label] == BLACK:
          answers[index] = representative[components.find(partner_label)]

      # fold node into its parent's set; the parent owns the new rep.
      parent: TreeNode[Label] | None = node.parent
      if parent is not None:
        components.union(parent.label, node.label)
        representative[components.find(parent.label)] = parent.label
  return answers

from collections.abc import Hashable, Iterable
from typing import Generic, TypeVar, cast


Element = TypeVar("Element", bound=Hashable)


class DisjointSetNode(Generic[Element]):
  """
    One element's node: its value, its parent link, and its rank.\n
    A node is its own parent exactly when it is the root of its set.\n
  """

  def __init__(self, value: Element) -> None:
    self.value: Element = value
    self.parent: DisjointSetNode[Element] = self
    self.rank: int = 0

  def __repr__(self) -> str:
    return f"DisjointSetNode({self.value!r})"


class UnionFind(Generic[Element]):
  """
    A collection of disjoint sets over hashable elements.\n
  """

  def __init__(self, elements: int | Iterable[Element] = 0) -> None:
    """
      Seed the structure. An int `n` creates singletons `0..n-1`;\n
      an iterable creates one singleton node per member.\n
    """
    # a seed count `n` means the elements are 0..n-1 (ints standing in for
    # Element); cast keeps the type checker happy about that substitution.
    members: Iterable[Element] = (
      cast("Iterable[Element]", range(elements))
      if isinstance(elements, int)
      else elements
    )
    # one singleton node per seeded member.
    self._nodes: dict[Element, DisjointSetNode[Element]] = {
      value: DisjointSetNode(value) for value in members
    }
    self.count: int = len(self._nodes)

  def add(self, value: Element) -> None:
    """
      Add `value` as a new singleton set if it is absent.\n
    """
    if value not in self._nodes:
      self._nodes[value] = DisjointSetNode(value)
      self.count += 1

  def _find_root(self, value: Element) -> DisjointSetNode[Element]:
    """
      The root node of `value`'s set, compressing the path on the way.\n
    """
    # first pass: climb parent links to the root of the set.
    node = self._nodes[value]
    root = node
    while root.parent is not root:
      root = root.parent

    # second pass: point every node on the path straight at the root.
    while node.parent is not root:
      node.parent, node = root, node.parent

    return root

  def find(self, value: Element) -> Element:
    """
      The representative value of `value`'s set.\n
    """
    return self._find_root(value).value

  def union(self, first: Element, second: Element) -> bool:
    """
      Merge the sets containing `first` and `second`.\n
      Returns False if they already shared a set.\n
    """
    # already in the same set: nothing to merge.
    first_root = self._find_root(first)
    second_root = self._find_root(second)
    if first_root is second_root:
      return False

    # hang the shorter tree under the taller one.
    if first_root.rank < second_root.rank:
      first_root, second_root = second_root, first_root
    second_root.parent = first_root

    # equal ranks: the merged tree grows one level taller.
    if first_root.rank == second_root.rank:
      first_root.rank += 1

    self.count -= 1
    return True

  def connected(self, first: Element, second: Element) -> bool:
    """
      Whether `first` and `second` belong to the same set.\n
    """
    return self._find_root(first) is self._find_root(second)

Pitfalls

Binary lifting is short to write and easy to get subtly wrong. The recurring bugs:

• $K$ too small. The table must reach the deepest possible climb: $2^K$ must be at least the tree height, and height can be $n-1$. Hard-coding K = 17 for $n\le 2\times 10^5$ ($2^{17}=131072<2\times 10^5$) fails exactly on path-shaped inputs — and only there, since random trees are shallow, so tests on random trees pass. Use $K=\lceil {\log }_{2}n\rceil$ (or $\lfloor {\log }_{2}n\rfloor +1$, which never under-shoots) and compute it from $n$.
• Off-by-one in the level loops. The columns are $0$ through $K$inclusive: the build loop runs $k=\mathrm{1..}K$ and the query loops touch bit $K$ and level $K$. Writing for k in 1..K-1 or scanning bits below $K$ silently halves the maximum jump, another bug invisible on shallow tests.
• Inconsistent root sentinel. Either $parent[root]=root$ (jumps saturate at the root, as in this lesson) or $parent[root]=\text{nil}$ (overshoots are detectable, but every build read must guard nil). With the saturating convention, $\text{Kth-Ancestor}$ cannot tell landed on the root from ran past it — compare $k$ with $depth[v]$ first if the difference matters. Mixing the two conventions dies on $up[\text{nil}][k]$.
• Skipping the coincidence check after phase 1. If equalizing depths makes $u=v$, that node is the LCA. Let phase 2 run anyway and every level test compares equal, so nothing jumps and the return $up[u][0]$ hands back the LCA's parent — one node too high.
• Jumping while $u\ne v$ instead of while $up[u][k]\ne up[v][k]$. The phase-2 test must look one jump ahead. Jumping whenever the current nodes differ lets a big jump land both on the LCA (or above it, where all ancestors agree), and the final $up[u][0]$ then overshoots. Keeping the nodes strictly below the LCA is the loop's invariant; the test enforces it.
• Building columns in the wrong order. $up[v][k]$ reads $up[\cdot ][k-1]$ at another node, so the whole of column $k-1$ must exist before column $k$ starts: the $k$ loop goes outside, the node loop inside. Swapping them reads half-built entries.

Constant-time LCA and where it hides

The theoretical optimum. Binary lifting answers each query in $O(\log n)$; the Euler-tour-plus-RMQ reduction in the alternatives above already reaches $O(1)$ per query after $O(n)$ preprocessing — the RMQ instance it produces has the special $\pm 1$ property (adjacent Euler-tour depths differ by exactly one), which the Bender-Farach-Colton method exploits to get true linear preprocessing.⁴ So LCA is, asymptotically, a solved problem: linear build, constant query. Binary lifting remains the common choice in practice anyway, because it also answers $k$-th ancestor and level-ancestor queries, is trivial to code correctly, and its $O(\log n)$ query is fast enough that the $O(1)$ machinery's larger constants rarely pay off.

Offline in near-linear total time. When every query is known in advance, Tarjan's offline algorithm answers all $q$ of them in one DFS with a union-find structure, for $O((n+q)\alpha (n))$ total — effectively linear.⁵ As DFS finishes a subtree it unions it into its parent's set, and a query $(u,v)$ is resolved the moment the second endpoint is reached: the answer is $\text{Find}$ of the other endpoint's set representative. It is the method of choice for batch workloads like compiler dominator trees and phylogenetics, where all queries arrive together.

Why LCA is everywhere. The lowest common ancestor is a primitive far beyond tree puzzles. Distance in a tree, $d(u,v)=depth(u)+depth(v)-2depth(\text{lca}(u,v))$, turns any path-length query into one LCA lookup. Suffix trees use LCA on the tree of suffixes to find the longest common extension of two positions in $O(1)$, which underlies fast string matching and the longest common prefix arrays of suffix automata. Version-control systems compute the merge base of two commits as an LCA in the commit DAG (generalized to directed acyclic graphs). And range-minimum queries and LCA are interreducible (each solves the other in linear time), so a fast LCA is also a fast RMQ and vice versa.

Takeaways

• The lowest common ancestor of $u$ and $v$ is the deepest node ancestral to both; it is unique because ancestor sets are root-chains.
• The naive walk (equalize depth, climb together) needs no preprocessing but costs $O(h)$ per query, or $\Theta (n)$ on a degenerate tree.
• Binary lifting precomputes $up[v][k]$, the $2^k$-th ancestor, via the doubling identity $up[v][k]=up[up[v][k-1]][k-1]$ in $O(n\log n)$ time and space.
• A $k$-th-ancestor query jumps by each $1$-bit of $k$; an LCA query lifts the deeper node to equal depth, then jumps both up by decreasing powers of two while they stay distinct — each $O(\log n)$.
• Tree distance is $depth[u]+depth[v]-2depth[\mathrm{lca}(u,v)]$, turning path queries into $O(\log n)$ arithmetic.
• Alternatives: Euler tour + sparse-table RMQ gives $O(1)$ queries on a static tree; Tarjan's union-find DFS answers all queries offline in near-linear time. Binary lifting wins on being online and also serving $k$-th ancestors.
• The classic bugs are boundary bugs — $K$ too small for path-shaped trees, levels looped to $K-1$, the missing $u=v$ check after depth equalization — and most stay invisible on random (hence shallow) test trees.