Binary Lifting Algorithm: Reach Any Tree Ancestor in O(log n)

You have a rooted tree with a million nodes. Someone asks a million times: "what is the deepest common ancestor of nodes u and v?" The naive algorithm walks both nodes to the root. That's O(n) per query, and on a tree that looks like a linked list it never gets better. For a million queries, you're looking at 10^12 operations. That number has twelve zeros. Your interviewer is not waiting for twelve zeros.

Binary lifting compresses any upward jump in a tree to O(log n) by precomputing a table of power-of-two ancestors. You spend O(n log n) once at startup, then answer every lowest common ancestor (LCA) query in O(log n). The same table, with zero extra code, also answers "what is the k-th ancestor of this node?" in O(log n).

The Problem With Walking Up

The Lowest Common Ancestor of two nodes u and v is the deepest node that is an ancestor of both. Think of it as the lowest manager on an org chart who oversees both employees. Formally: LCA(u, v) is the node w such that w is an ancestor of both u and v, and no child of w is an ancestor of both.

The naive LCA algorithm needs two walks. Walk u to the root, recording every node in a set. Walk v to the root, stopping at the first node already in the set. That first hit is the LCA.

On a balanced binary tree of height log n, this runs in O(log n). Fine. But trees in problems are rarely balanced. Contest setters know this. The first example is always a nice balanced binary tree. Test case 30 is a linked list. On a path graph rooted at one end, every node is at depth O(n), and LCA of the two deepest nodes requires O(n) work. With q queries, the total is O(n * q). At n = q = 10^5 that's 10^10 operations. Not happening.

The key observation that unlocks efficiency: any integer k can be written as a sum of distinct powers of two. In binary, 37 is 100101, so 37 = 32 + 4 + 1. Three jumps, not 37. And any k needs at most ⌊log₂(k)⌋ + 1 of them. If you precompute every power-of-two ancestor, any climb costs O(log n).

Building the Table

Define up[j][v] as the ancestor of v that is exactly 2^j levels above v. The base case is straightforward: up[0][v] is v's parent. The root's parent is the root itself, forming a sentinel that stops any overshoot.

The recurrence is the key insight:

up[j][v] = up[j-1][ up[j-1][v] ]

"The 2^j-th ancestor of v is the 2^(j-1)-th ancestor of v's 2^(j-1)-th ancestor." Jump halfway, then jump the other half. This is the same doubling trick used in the sparse table for range minimum queries.

To build the table, first run a DFS to compute depths and fill up[0][] (parents). Then fill each level j from 1 to LOG-1, iterating over all nodes at each level. The outer loop must be over j (levels), not over v (nodes), because filling up[j][v] requires up[j-1][...] to be fully computed. Get this backwards and the table fills with garbage. The first query will look suspiciously correct. The second will not.

# Build up[0] during DFS, then fill higher levels
for j in range(1, LOG):
    for v in range(1, n + 1):
        up[j][v] = up[j - 1][up[j - 1][v]]

Time complexity for preprocessing: O(n log n). There are LOG = O(log n) levels, each requiring a pass over all n nodes. Space: O(n log n) for the table itself plus O(n) for depths. For n = 10^6 with LOG = 20 and 32-bit integers, the table occupies 20 * 10^6 * 4 = 80 MB. Fine for most contest environments. Less fine if the online judge prints "Memory Limit Exceeded" with no further explanation five minutes before the contest ends.

The table for a small tree makes the structure visible. Each column is a node, each row doubles the distance.

The example tree: root at node 1, depth 0. Nodes 8 and 9 sit at depth 3 under node 6.

          node:  1   2   3   4   5   6   7   8   9
up[0] (2^0=1):   1   1   1   2   2   3   3   6   6
up[1] (2^1=2):   1   1   1   1   1   1   1   3   3
up[2] (2^2=4):   1   1   1   1   1   1   1   1   1

Reading: node 8's parent is 6, its grandparent is 3, its 4th ancestor is 1 (root). Node 9's parent is also 6.

The lifting table. Amber values point to intermediate ancestors (the interesting ones). Grey values are all roads leading to root.

Finding the LCA: Two Phases

The query algorithm for LCA(u, v) runs in two phases. Both take O(log n).

Phase 1: bring both nodes to the same depth. Without loss of generality, say depth[u] >= depth[v]. Compute diff = depth[u] - depth[v]. Write diff in binary and apply the corresponding jumps to u.

diff = depth[u] - depth[v]
for j in range(LOG):
    if (diff >> j) & 1:
        u = up[j][u]

After this loop, u and v are at the same depth. If u == v, then v was an ancestor of u all along. Return it immediately.

Phase 2: binary search for the divergence point. Now u and v are at the same depth, and LCA is somewhere above. Walk both upward simultaneously from the highest possible jump, only jumping when the destinations still differ.

for j in range(LOG - 1, -1, -1):
    if up[j][u] != up[j][v]:
        u = up[j][u]
        v = up[j][v]
return up[0][u]

The loop goes high-to-low (LOG-1 down to 0). It jumps only when the ancestors diverge, meaning we haven't yet passed the LCA. After the loop, u and v are each one step below the LCA. up[0][u] is the LCA.

Here is a step-by-step trace of LCA(8, 9) on the example tree (root = 1, depth[8] = depth[9] = 3):

Phase 1: same depth, diff = 0, no jumps.
u = 8, v = 9. u != v, proceed to phase 2.

Phase 2 (j = LOG-1 down to 0):
j=2: up[2][8] = 1, up[2][9] = 1. Equal, skip.
j=1: up[1][8] = 3, up[1][9] = 3. Equal, skip.
j=0: up[0][8] = 6, up[0][9] = 6. Equal, skip.

Return up[0][8] = 6.

LCA(8, 9) = 6. Correct: both 8 and 9 are children of 6.

Now trace LCA(5, 8), where depth[5] = 2 and depth[8] = 3:

Phase 1: u = 8 (deeper), diff = 1 = binary "1".
j=0: bit set, u = up[0][8] = 6. Now depth[u] = depth[v] = 2.
u = 6, v = 5. u != v, proceed.

Phase 2:
j=LOG-1..1: up[j][6] = up[j][5] = 1 for j >= 1. Equal, skip.
j=0: up[0][6] = 3, up[0][5] = 2. Different! u = 3, v = 2.

Return up[0][3] = 1.

LCA(5, 8) = 1. The root. Correct: 5 lives under node 2, 8 lives under node 6, and they share only the root as an ancestor.

LCA(8, 5): node 8 jumps one level in Phase 1 to equalize depths. Phase 2 binary-searches until nodes 6 and 5 are one step below the shared root.

Why Phase 2 Is Correct

The invariant throughout phase 2 is: u and v are always strictly below the LCA, and they are always distinct. We enter phase 2 knowing u != v (we checked after phase 1). We only jump when the destinations differ, so we never land on or above the LCA during a jump.

After all LOG iterations, u and v are as high as they can be while still being distinct. They're each exactly one step below the LCA. Think of it as two engineers who escalated the same incident ticket all the way up the org chart. Both now standing exactly one floor below the shared manager. Both still blaming each other. If they could go one more step (with j=0) and still be distinct, the loop would have taken that step. Since it didn't, up[0][u] == up[0][v] is the LCA.

Let k be the number of steps from u to LCA. Write k in binary. Processing bits from high to low either skips (the jump would overshoot into or above LCA) or takes the step (still below). After processing all bits, the total steps taken equals k exactly, landing u and v each one below LCA.

The directional constraint matters: the loop must go from high j to low j. Going low-to-high would misidentify which bits to set, potentially overshooting.

Complexity at a Glance

Compared to alternatives:

Binary lifting is the default choice in competitive programming. It codes up under time pressure, handles k-th ancestor for free, and does not require you to explain what "Bender-Farach-Colton" means.

The k-th Ancestor Is Free

The binary lifting table directly answers "what is the k-th ancestor of node v?" Write k in binary. Apply the corresponding jumps. You already wrote this code. It's phase 1 of LCA applied to a single node.

def kth_ancestor(v: int, k: int) -> int:
    for j in range(LOG):
        if (k >> j) & 1:
            v = up[j][v]
    return v  # returns root if k > depth[v]

If k exceeds depth[v], repeated jumps reach the root and stay there (because up[j][root] = root). O(log n) time, no extra space.

Beyond LCA: Weighted Binary Lifting

The table can carry additional information alongside the ancestor pointer. For a tree with weighted edges, define a parallel table up_max[j][v] = maximum edge weight on the path from v to its 2^j-th ancestor. Fill it with the same recurrence:

up_max[0][v] = weight_of_edge(v, parent[v])
up_max[j][v] = max(up_max[j-1][v], up_max[j-1][up[j-1][v]])

During an LCA query, carry the running aggregate alongside the jumps. This gives you the maximum (or minimum, or sum) edge weight on any tree path in O(log n). Useful for bottleneck path problems and minimum-spanning-path queries.

Any associative function over path edges can be tracked this way. Minimum edge, sum of edge weights, product of edge weights, XOR of edge weights. The requirement is that the function composes over ranges: f(path u to v) = f(path u to mid) op f(path mid to v).

One Structure, Every Language

Each implementation below takes n (number of nodes, 1-indexed), root, and the edge list. It builds the binary lifting table during construction and exposes lca(u, v) and kth_ancestor(v, k) queries.

from collections import defaultdict

class BinaryLifting:
    def __init__(self, n: int, root: int, edges: list[tuple[int, int]]):
        self.LOG = max(1, n.bit_length())
        adj: dict[int, list[int]] = defaultdict(list)
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        self.depth = [0] * (n + 1)
        self.up = [[0] * (n + 1) for _ in range(self.LOG)]

        stack = [(root, root)]
        visited = [False] * (n + 1)
        while stack:
            v, parent = stack.pop()
            if visited[v]:
                continue
            visited[v] = True
            self.up[0][v] = parent
            for u in adj[v]:
                if not visited[u]:
                    self.depth[u] = self.depth[v] + 1
                    stack.append((u, v))

        for j in range(1, self.LOG):
            for v in range(1, n + 1):
                self.up[j][v] = self.up[j - 1][self.up[j - 1][v]]

    def lca(self, u: int, v: int) -> int:
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        diff = self.depth[u] - self.depth[v]
        for j in range(self.LOG):
            if (diff >> j) & 1:
                u = self.up[j][u]
        if u == v:
            return u
        for j in range(self.LOG - 1, -1, -1):
            if self.up[j][u] != self.up[j][v]:
                u = self.up[j][u]
                v = self.up[j][v]
        return self.up[0][u]

    def kth_ancestor(self, v: int, k: int) -> int:
        for j in range(self.LOG):
            if (k >> j) & 1:
                v = self.up[j][v]
        return v

What Problems Does This Solve?

Binary lifting and LCA show up whenever a problem needs to reason about relationships between nodes on a tree path. The core problem classes:

Distance between two nodes. dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA(u, v)]. Each query is O(log n). With range minimum query on the depth array (Euler tour reduction), you can get O(1) per query, but binary lifting's O(log n) is fast enough for most constraints.

Path aggregates. Maximum edge weight between u and v. Minimum bottleneck. Sum of edge weights. All solvable by extending the lifting table as described in the weighted binary lifting section above.

Node on a path. Given two nodes u and v, find the node exactly k steps from u toward v. Compute LCA, decompose the path into u-to-LCA and LCA-to-v segments, use k-th ancestor on the appropriate segment.

Counting nodes in subtrees with queries. Many problems involve "how many nodes in the subtree of v satisfy property P?" Binary lifting composes with Euler tour timestamps (in-time and out-time) for efficient range queries on subtrees.

Tree path queries in general. If a problem says "for each query, process the path between two nodes in a tree," binary lifting handles the decomposition into O(log n) jumps so you can apply an aggregation function.

How to Spot a Binary Lifting Problem

Some patterns knock on the door politely. Binary lifting kicks it down. Two strong signals:

You see "tree" and "queries about ancestors or paths." Any time a problem gives you a rooted tree and asks about LCA, k-th ancestor, or path aggregates with n and q in the range 10^5 to 10^6, binary lifting is your default. The O(n log n) preprocessing is cheap; the O(log n) per query is fast.

The constraint block says 1 <= k <= n alongside a tree. The k-th ancestor problem is one of the clearest pattern signals in competitive programming. When you see "given a tree, find the k-th ancestor of node v," binary lifting is the answer.

Worked Example 1: Tree Distances (LeetCode 2385 variant)

Problem: Given a tree of n nodes rooted at node 1 and q queries each asking for the distance between nodes u and v, answer all queries in O((n + q) log n).

Why binary lifting fits: distance between two nodes in a tree is exactly depth[u] + depth[v] - 2 * depth[LCA(u, v)]. Computing LCA is the bottleneck. With O(n log n) preprocessing and O(log n) per LCA query, total is O((n + q) log n). Compare to naive, which would be O(n * q).

The key step is recognizing that "distance in a tree" = "depth of both minus twice the depth of their meeting point." Once you see that shape, LCA is inevitable.

Worked Example 2: Kth Ancestor of a Tree Node (LeetCode 1483)

Problem: Given a tree with n nodes, implement getKthAncestor(node, k) in O(n log n) time to build and O(log n) time per query.

This is the k-th ancestor problem verbatim. The brute force: walk k steps upward. O(n) per query, O(n^2) total for n queries. Binary lifting: write k in binary, apply the precomputed jumps. O(log n) per query.

The one subtlety: when k exceeds the depth of the node, the correct answer is typically -1 (the node has no k-th ancestor). The sentinel approach returns the root instead. Add a depth check:

def getKthAncestor(self, node: int, k: int) -> int:
    if k > self.depth[node]:
        return -1
    return self.kth_ancestor(node, k)

One line of guard logic, and you're done.

What You Should Know Cold

Here is what you need to be able to say without looking anything up. Write this on a mental whiteboard before you open any IDE.

• What it is: A precomputed table where up[j][v] stores the 2^j-th ancestor of v.
• Recurrence: up[j][v] = up[j-1][up[j-1][v]]. Any climb decomposes into at most log n power-of-two jumps.
• Preprocessing: O(n log n) time, O(n log n) space. Build with iterative DFS then a double loop over levels.
• LCA query: O(log n). Phase 1 equalizes depths using binary decomposition of the difference. Phase 2 binary-searches for the divergence point from high bits to low.
• k-th ancestor: O(log n) for free, using the same table. Phase 1 alone, applied to a single node.
• Root sentinel: up[j][root] = root for all j. Prevents out-of-bounds when lifting past the root.
• LOG: ⌊log₂(n)⌋ + 1. Use LOG = 20 for n up to 10^6, LOG = 18 for n up to 262144.
• Watch the loop direction in phase 2: Always high-to-low. Low-to-high breaks the binary search invariant.
• Weighted extension: Store a parallel table of aggregates alongside up[][] for O(log n) path min/max/sum queries.
• Alternatives: Euler tour + sparse table gives O(1) LCA queries but does not support k-th ancestor and has more setup code. Tarjan offline is faster in total but requires all queries upfront.

Knowing all this cold is half the battle. The other half is explaining it out loud while someone watches through a video call. If you want to practice narrating your way through tree problems with a real feedback rubric, SpaceComplexity runs voice-based mock DSA interviews. The score is on how well you identify the structure, not just whether the code compiles.

Further Reading

• Lowest common ancestor, Wikipedia
• Level ancestor problem, Wikipedia
• LCA in a tree using binary lifting, GeeksforGeeks
• Binary lifting guide, GeeksforGeeks
• Tarjan's offline LCA algorithm, GeeksforGeeks