---
title: Lowest Common Ancestor & Binary Lifting
module: Graphs
moduleNumber: 6
lessonNumber: 11
order: 611
summary: |
  Given a rooted tree, the lowest common ancestor of $u$ and $v$ is the deepest
  node that is an ancestor of both. A naive walk answers one query in $O(h)$;
  **binary lifting** precomputes the $2^k$-th ancestor of every node in
  $O(n\log n)$, then answers $k$-th-ancestor and LCA queries in $O(\log n)$ each.
  We derive both jumps, apply them to tree distance, and compare against the
  Euler-tour + RMQ and Tarjan offline alternatives.
topics: [Graphs]
sources:
  - book: CLRS
    ref: "Ch. — (trees)"
  - book: Skiena
    ref: "§ — Trees / LCA"
  - book: Erickson
    ref: "Ch. — Trees"
practice:
  - title: 'Lowest Common Ancestor of a Binary Tree'
    slug: lowest-common-ancestor-of-a-binary-tree
    difficulty: Medium
  - title: 'Kth Ancestor of a Tree Node'
    slug: kth-ancestor-of-a-tree-node
    difficulty: Hard
  - title: 'Step-By-Step Directions From a Binary Tree Node to Another'
    slug: step-by-step-directions-from-a-binary-tree-node-to-another
    difficulty: Medium
  - title: 'Smallest Common Region'
    slug: smallest-common-region
    difficulty: Medium
---

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**.

> **Definition.** Fix a root $r$ of a tree $T$. A node $a$ is an **ancestor** of
> $v$ if $a$ lies on the path from $r$ to $v$ (every node is its own ancestor).
> The **lowest common ancestor** $\lca(u,v)$ is the ancestor of
> both $u$ and $v$ that is **deepest** — farthest from the root.

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.

::impl{algo="rooted_tree"}

## 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.

```algorithm
caption: $\textsc{Naive-LCA}(u, v)$ — climb to equal depth, then together
while $depth[u] > depth[v]$ do
  $u \gets parent[u]$
while $depth[v] > depth[u]$ do
  $v \gets parent[v]$
while $u \ne v$ do
  $u \gets parent[u]$
  $v \gets parent[v]$
return $u$
```

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](/algorithms/foundations/asymptotic-analysis).)

::impl{algo="naive_lca"}

## 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.

> **Definition.** Let $up[v][k]$ be the $2^k$-th ancestor of $v$, the node
> reached by following parent pointers $2^k$ times (or the root, if that would
> climb past it). In particular $up[v][0] = parent[v]$.

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

> **Lemma (doubling).** For $k \ge 1$,
> $$up[v][k] = up\brackets{\,up[v][k-1]\,}[k-1].$$
>

> **Proof.** $up[v][k-1]$ is $2^{k-1}$ edges above $v$; applying the same jump to it
> climbs another $2^{k-1}$ edges, for $2^{k-1} + 2^{k-1} = 2^k$ total. $\qed$

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.

```algorithm
caption: $\textsc{Build-Up}(T)$ — preprocess $2^k$-th ancestors via doubling
run a DFS/BFS from the root to fill $parent[\cdot]$ and $depth[\cdot]$
for each node $v$ do
  $up[v][0] \gets parent[v]$  // root points to itself
for $k \gets 1$ to $K$ do
  for each node $v$ do
    $up[v][k] \gets up[\,up[v][k-1]\,][k-1]$
```

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.

$$
% caption: doubling identity: $up[v][2]$ (a $4$-edge climb) is two $up[\cdot][1]$ jumps of
%          $2$ edges each
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (v)  at (0,0)    {$v$};
  \node (n1) at (0,-1.0) {};
  \node (m)  at (0,-2.0) {$m$};
  \node (n3) at (0,-3.0) {};
  \node (w)  at (0,-4.0) {$w$};
  \draw (v)--(n1)--(m)--(n3)--(w);
  \draw[->, acc, thick, bend left=60] (v) to node[draw=none, right=1mm, font=\footnotesize, text=acc]{$2^1$} (m);
  \draw[->, acc, thick, bend left=60] (m) to node[draw=none, right=1mm, font=\footnotesize, text=acc]{$2^1$} (w);
  \draw[->, thick, bend right=55] (v) to node[draw=none, left=1mm, font=\footnotesize]{$2^2=up[v][2]$} (w);
\end{tikzpicture}
$$

### $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`.

```algorithm
caption: $\textsc{Kth-Ancestor}(v, k)$ — jump by each 1-bit of $k$
for $j \gets 0$ to $K$ do
  if $k$ has bit $j$ set then
    $v \gets up[v][j]$
    if $v = \text{nil}$ then return nil  // ran off the root
return $v$
```

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.

$$
% caption: $5=101_2$ splits the $5$-edge climb into a $2^0$ jump then a $2^2$ jump (one
%          per set bit)
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (v)  at (0,0)    {$v$};
  \node (a1) at (0,-0.95){};
  \node (a2) at (0,-1.9) {};
  \node (a3) at (0,-2.85){};
  \node (a4) at (0,-3.8) {};
  \node (a5) at (0,-4.75){};
  \draw (v)--(a1)--(a2)--(a3)--(a4)--(a5);
  \draw[->, acc, thick, bend left=70] (v)  to node[draw=none, right=1mm, font=\footnotesize, text=acc]{$2^0$} (a1);
  \draw[->, acc, thick, bend right=45] (a1) to node[draw=none, left=1mm, font=\footnotesize, text=acc]{$2^2$} (a5);
  \node[draw=none, font=\footnotesize] at (2.0,-2.85) {$5 = 101_2$};
\end{tikzpicture}
$$

### 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 $\textsc{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.

```algorithm
caption: $\textsc{LCA}(u, v)$ — equalize depth, then jump both up greedily
if $depth[u] < depth[v]$ then swap $u, v$
$u \gets \textsc{Kth-Ancestor}(u,\ depth[u] - depth[v])$  // phase 1
if $u = v$ then return $u$
for $k \gets K$ downto $0$ do                              // phase 2
  if $up[u][k] \ne up[v][k]$ then
    $u \gets up[u][k]$
    $v \gets up[v][k]$
return $up[u][0]$  // their common parent
```

> **Remark (Why high-to-low greedy is correct).** Let $d$ be the number of edges from the
> equalized $u$ up to the LCA (the same for $v$). We must climb $u$ and $v$ up by
> exactly $d-1$, stopping one short so they land on the LCA's two distinct
> descendants, and then take one parent step. Scanning $k$ from high to low and
> jumping whenever the targets _differ_ is the greedy construction of
> $d-1$ in binary: a jump of $2^k$ is taken iff it does not overshoot the LCA
> (overshooting would make $up[u][k]$ and $up[v][k]$ equal). It is the same
> high-to-low bit selection used throughout binary lifting.

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.

$$
% caption: Lift the deeper node to equal depth, then jump both up by decreasing powers of
%          two; the LCA is highlighted
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  level distance=11mm, sibling distance=15mm, >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (r) {$r$}
    child {node (a) {$a$}
      child {node (l) {$c$}
        child {node (u) {$u$}}
        child[missing]
      }
      child {node (b) {$b$}
        child {node (v) {$v$}}
        child[missing]
      }
    }
    child[missing];
  \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (a) {};
  \draw[->, acc, thick, dashed, bend left=20] (u) to (l);
  \draw[->, acc, thick, dashed, bend left=25] (l) to (a);
  \draw[->, acc, thick, dashed, bend right=25] (v) to (b);
  \draw[->, acc, thick, dashed, bend right=25] (b) to (a);
\end{tikzpicture}
$$

Here $u$ and $v$ already share depth; both lift to $c$ and $b$ (kept distinct),
then one parent step lands on $a = \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$.

$$
% caption: The worked tree, rooted at $1$. Node $11$ is deepest at depth $5$; nodes $9$
%          and $12$ share depth $4$ in different subtrees.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (n1)  at (3.2,0)     {$1$};
  \node (n2)  at (1.6,-0.95) {$2$};
  \node (n3)  at (4.8,-0.95) {$3$};
  \node (n4)  at (0.8,-1.9)  {$4$};
  \node (n5)  at (2.6,-1.9)  {$5$};
  \node (n6)  at (4.8,-1.9)  {$6$};
  \node (n7)  at (0.2,-2.85) {$7$};
  \node (n8)  at (2.0,-2.85) {$8$};
  \node (n10) at (4.8,-2.85) {$10$};
  \node (n9)  at (0.2,-3.8)  {$9$};
  \node (n12) at (4.8,-3.8)  {$12$};
  \node (n11) at (0.2,-4.75) {$11$};
  \draw (n1)--(n2); \draw (n1)--(n3);
  \draw (n2)--(n4); \draw (n2)--(n5); \draw (n3)--(n6);
  \draw (n4)--(n7); \draw (n4)--(n8); \draw (n6)--(n10);
  \draw (n7)--(n9); \draw (n10)--(n12);
  \draw (n9)--(n11);
  \foreach \d in {0,...,5}
    \node[draw=none, font=\footnotesize, text=black] at (-1.3,{-0.95*\d}) {depth \d};
\end{tikzpicture}
$$

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 $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.

$$
% caption: The full $up[v][k]$ table for the worked tree. Column $0$ is the parent array;
%          each later column composes the previous one with itself. The two cells in acc
%          are the jumps of the query "$5$th ancestor of $11$" ($5 = 101_2$).
\begin{tikzpicture}[
  cell/.style={draw, minimum width=10mm, minimum height=6mm, inner sep=1pt, font=\small},
  hd/.style={minimum width=10mm, minimum height=6mm, inner sep=1pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[hd] at (0,0) {node};
  \node[hd] at (1.0,0) {$k{=}0$};
  \node[hd] at (2.0,0) {$k{=}1$};
  \node[hd] at (3.0,0) {$k{=}2$};
  \node[hd] at (4.0,0) {$k{=}3$};
  \foreach \i/\nd/\a/\b/\c/\d in {
    1/1/1/1/1/1, 2/2/1/1/1/1, 3/3/1/1/1/1, 4/4/2/1/1/1,
    5/5/2/1/1/1, 6/6/3/1/1/1, 7/7/4/2/1/1, 8/8/4/2/1/1,
    9/9/7/4/1/1, 10/10/6/3/1/1, 11/11/9/7/2/1, 12/12/10/6/1/1}{
    \node[cell] at (0,{-0.6*\i}) {$\nd$};
    \node[cell] at (1.0,{-0.6*\i}) {$\a$};
    \node[cell] at (2.0,{-0.6*\i}) {$\b$};
    \node[cell] at (3.0,{-0.6*\i}) {$\c$};
    \node[cell] at (4.0,{-0.6*\i}) {$\d$};
  }
  \node[cell, draw=acc, very thick] at (1.0,-6.6) {};
  \node[cell, draw=acc, very thick] at (3.0,-5.4) {};
\end{tikzpicture}
$$

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. $\textsc{Kth-Ancestor}$ scans the bits low to high:

- bit $0$ set: $v \gets up[11][0] = 9$: climbed $1$ edge, $4$ to go;
- bit $1$ clear: skip column $1$;
- bit $2$ set: $v \gets 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 $\textsc{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 \gets 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 \gets 4$, $v \gets 6$, both now at depth $2$.
- $k=0$: $up[4][0] = 2$ and $up[6][0] = 3$ — **different** again: $u \gets 2$,
  $v \gets 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 $\lca(11,12) = 1$.

$$
% caption: $\textsc{LCA}(11,12)$ on the worked tree: the phase-1 lift ($2^0$), then the
%          taken phase-2 jumps ($2^1$ then $2^0$ on both sides). The loop stops at $2$ and
%          $3$, the two children of the answer $up[2][0]=1$, ringed in acc.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node (n1)  at (3.2,0)     {$1$};
  \node (n2)  at (1.6,-0.95) {$2$};
  \node (n3)  at (4.8,-0.95) {$3$};
  \node (n4)  at (0.8,-1.9)  {$4$};
  \node (n5)  at (2.6,-1.9)  {$5$};
  \node (n6)  at (4.8,-1.9)  {$6$};
  \node (n7)  at (0.2,-2.85) {$7$};
  \node (n8)  at (2.0,-2.85) {$8$};
  \node (n10) at (4.8,-2.85) {$10$};
  \node (n9)  at (0.2,-3.8)  {$9$};
  \node (n12) at (4.8,-3.8)  {$12$};
  \node (n11) at (0.2,-4.75) {$11$};
  \draw (n1)--(n2); \draw (n1)--(n3);
  \draw (n2)--(n4); \draw (n2)--(n5); \draw (n3)--(n6);
  \draw (n4)--(n7); \draw (n4)--(n8); \draw (n6)--(n10);
  \draw (n7)--(n9); \draw (n10)--(n12);
  \draw (n9)--(n11);
  \node[draw=acc, very thick, minimum size=7mm, inner sep=0] at (n1) {};
  \draw[->, acc, thick, dashed] (n11) to[bend left=45]
    node[draw=none, left=0.5mm, font=\footnotesize, text=acc]{$2^0$} (n9);
  \draw[->, acc, thick] (n9) to[bend right=40]
    node[draw=none, pos=0.35, right=0.5mm, font=\footnotesize, text=acc]{$2^1$} (n4);
  \draw[->, acc, thick] (n4) to[bend right=35]
    node[draw=none, right=0.5mm, font=\footnotesize, text=acc]{$2^0$} (n2);
  \draw[->, acc, thick] (n12) to[bend right=40]
    node[draw=none, right=0.5mm, font=\footnotesize, text=acc]{$2^1$} (n6);
  \draw[->, acc, thick] (n6) to[bend right=35]
    node[draw=none, right=0.5mm, font=\footnotesize, text=acc]{$2^0$} (n3);
\end{tikzpicture}
$$

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 $\lca(u,v)$ and back
down to $v$, so its length is

$$
\dist(u,v) = depth[u] + depth[v] - 2\,depth\brackets{\lca(u,v)}.
$$

On the worked tree, $\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 $\textsc{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$.

::impl{algo="binary_lifting"}

## Alternatives

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

- **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**](/algorithms/data-structures/fenwick-and-segment-trees) over the depth array, which a
  sparse table answers in $O(1)$ after an $O(n\log n)$ build.[^euler] 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$:

  $$
  % caption: Euler tour reduces LCA to range-minimum: between $u$ and $v$ in the tour, the shallowest (minimum-depth) entry is $\lca(u,v)=a$.
  \begin{tikzpicture}[font=\small, >=Stealth, x=8.5mm]
    \definecolor{acc}{HTML}{2348F2}
    % --- small tree ---
    \begin{scope}[every node/.style={circle, draw, minimum size=6mm, inner sep=0pt, font=\scriptsize}]
      \node (r) at (3,1.7) {$r$};
      \node (a) at (3,0.85) {$a$};
      \node (uu) at (2.3,0) {$u$};
      \node (vv) at (3.7,0) {$v$};
      \draw (r)--(a); \draw (a)--(uu); \draw (a)--(vv);
    \end{scope}
    % shade the subarray between u (idx 2) and v (idx 4) -- drawn first, behind cells
    \fill[acc!16] (2-0.45,-1.35) rectangle (4+0.45,-0.65);
    % --- euler tour array + depths ---
    \foreach \lab [count=\i from 0] in {r,a,u,a,v,a,r}
      \node[draw, minimum size=6mm, font=\scriptsize] at (\i,-1.0) {$\lab$};
    \foreach \dpt [count=\i from 0] in {0,1,2,1,2,1,0}
      \node[font=\scriptsize, text=black] at (\i,-1.75) {$\dpt$};
    % mark the minimum-depth entry (a at idx 3)
    \node[draw=acc, very thick, minimum size=6mm, inner sep=0] at (3,-1.0) {};
    \node[font=\scriptsize, text=black] at (-1.3,-1.0) {tour:};
    \node[font=\scriptsize, text=black] at (-1.3,-1.75) {depth:};
    \node[font=\scriptsize, acc] at (3,-2.45) {min depth $=\lca=a$};
  \end{tikzpicture}
  $$

  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 $\lca(4,6)$ spans tour indices $2$
  through $8$ — length $7$, block length $2^{\lfloor\log_2 7\rfloor} = 4$:

  $$
  % caption: Sparse-table RMQ in $O(1)$: the range $[2,8]$ between the occurrences of $4$
  %          and $6$ is covered by two overlapping length-$4$ blocks $L=[2,5]$ and
  %          $R=[5,8]$, both precomputed. $\min(\min L, \min R) = \min(1, 0) = 0$ at index
  %          $6$: node $1 = \lca(4,6)$.
  \begin{tikzpicture}[font=\small, >=stealth, x=8.5mm]
    \definecolor{acc}{HTML}{2348F2}
    \foreach \ix [count=\i from 0] in {0,1,2,3,4,5,6,7,8,9,10}
      \node[font=\scriptsize, text=black] at (\i,0.75) {$\ix$};
    \foreach \lab [count=\i from 0] in {1,2,4,2,5,2,1,3,6,3,1}
      \node[draw, minimum size=6mm, font=\scriptsize] at (\i,0) {$\lab$};
    \foreach \dpt [count=\i from 0] in {0,1,2,1,2,1,0,1,2,1,0}
      \node[font=\scriptsize, text=black] at (\i,-0.75) {$\dpt$};
    \node[draw=acc, very thick, minimum size=6mm, inner sep=0] at (6,0) {};
    \draw[acc, thick] (1.65,1.35) -- (5.35,1.35)
      node[midway, above, font=\scriptsize, text=acc] {$L$};
    \draw[acc, thick] (1.65,1.25) -- (1.65,1.45);
    \draw[acc, thick] (5.35,1.25) -- (5.35,1.45);
    \draw[acc, thick] (4.65,-1.3) -- (8.35,-1.3)
      node[midway, below, font=\scriptsize, text=acc] {$R$};
    \draw[acc, thick] (4.65,-1.2) -- (4.65,-1.4);
    \draw[acc, thick] (8.35,-1.2) -- (8.35,-1.4);
    \node[font=\scriptsize, text=black] at (-1.3,0.75) {index:};
    \node[font=\scriptsize, text=black] at (-1.3,0) {tour:};
    \node[font=\scriptsize, text=black] at (-1.3,-0.75) {depth:};
  \end{tikzpicture}
  $$

  Block $L$ covers indices $2..5$ with depth minimum $1$; block $R$ covers
  $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](/algorithms/graphs/representations-and-traversal)
  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.[^tarjan]

::impl{algo="euler_tour_rmq_lca,tarjan_offline_lca"}

> **Remark (How to choose).** Binary lifting is **online** (queries may arrive one at a
> time), needs only parent pointers and a DFS, answers in $O(\log n)$, and is the
> _only_ one of the three that also serves $k$-th-ancestor queries — at the cost
> of $O(n\log n)$ space. Reach for Euler+RMQ when you need $O(1)$ LCA on a fixed
> tree, and Tarjan when every query is known up front and you want the lowest
> total cost.

## 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 = 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, $\textsc{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.[^bfc] 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](/algorithms/data-structures/union-find) structure, for $O((n + q)\,\alpha(n))$ total — effectively linear.[^tarjan-lca] 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 $\textsc{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) - 2\,depth(\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] - 2\,depth[\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.

[^cprefs]: **Skiena**, § — Trees / LCA: survey of LCA strategies and the preprocessing/query trade-off across query models.
[^euler]: **Erickson**, Ch. — Trees: the Euler-tour reduction of LCA to range-minimum, with sparse-table RMQ giving $O(1)$ queries after $O(n\log n)$ preprocessing.
[^tarjan]: **CLRS**, Ch. — (trees): Tarjan's offline LCA via depth-first search and disjoint-set union, near-linear in $(n+q)$.
[^bfc]: **Bender, M. A. & Farach-Colton, M.** (2000), "The LCA Problem Revisited," _Proc. LATIN 2000_, 88–94 — linear-preprocessing, constant-query LCA via the $\pm 1$ RMQ reduction.
[^tarjan-lca]: **Tarjan, R. E.** (1979), "Applications of path compression on balanced trees," _Journal of the ACM_ 26(4), 690–715 — the offline union-find LCA algorithm.