Skip to content
Tutorials Center
My learning

Topics

Lesson 103 of 225 ยท Trees

Binary Lifting and Lowest Common Ancestor

Learn binary lifting in Python: build jump pointers in O(n log n), find the k-th ancestor and the lowest common ancestor in O(log n), and compute tree distances.

In a tree you often need to travel upward quickly. Who is the grandparent of this node? The 1,000th ancestor? Where do the paths from two nodes first meet? Walking one parent at a time costs O(depth), and a tree shaped like a long path has depth n. If you must answer many questions, that is far too slow.

Binary lifting fixes this with a simple trick. Instead of storing only each node's parent (one step up), store the ancestor 1, 2, 4, 8, ... steps up. Any distance is a sum of powers of two (its binary representation), so any upward trip takes O(log n) jumps. The same table also answers lowest common ancestor (LCA) queries in O(log n), after O(n log n) preprocessing.

The jump table

Let up[j][v] be the ancestor of v that is 2^j steps above. If a node has fewer than 2^j ancestors, store a sentinel (we use the root itself, which is its own parent, so jumping past the top keeps you at the root).

  • up[0][v] is the parent of v.
  • up[j][v] = up[j-1][ up[j-1][v] ]: to go 2^j steps, go 2^(j-1) steps twice.

The second rule is the whole trick: each row is computed from the previous row in O(n). With LOG = 17 rows you cover trees up to 131,072 nodes deep; use n.bit_length() rows in general.

For a path 0-1-2-...-8 (root 0), the jumps from node 8 look like this:

flowchart LR
    n8((8)) -->|"2^0"| n7((7))
    n8 -->|"2^1"| n6((6))
    n8 -->|"2^2"| n4((4))
    n8 -->|"2^3"| n0((0))

Jump pointers from node 8: one, two, four and eight steps up. To go 6 steps, take the 2-jump and then the 4-jump (6 = 110 in binary).

Python Build the table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Memory is n * log n integers. For one million nodes that is about 20 million entries, which is fine in C++ but heavy for plain Python lists; see the notes at the end.

k-th ancestor in O(log n)

To move v up by k steps, look at the binary digits of k. For every set bit j, jump v = up[j][v]. The order of jumps does not matter, because the total is the same.

For k = 6 (binary 110), jump 4, then 2. Because the table sticks at the root, asking for more steps than the depth just returns the root; you can check k > depth[v] first if you want to report "no such ancestor".

Python Jump by any distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lowest common ancestor

The LCA of u and v is the deepest node that is an ancestor of both (a node counts as its own ancestor). It is where the two root paths first merge.

Binary lifting finds it in two phases:

  1. Equalize depths. If depth[u] > depth[v], lift u by depth[u] - depth[v]. Now both are at the same depth. If they are the same node, that node is the answer.
  2. Lift together. For j from the highest power down to 0, if up[j][u] != up[j][v], jump both u and v. These jumps land on nodes that are still below the LCA, because jumping onto the LCA would make the two ancestors equal. After the loop, u and v are different children of the LCA, so the answer is up[0][u].
flowchart TD
    A["lca(u, v)"] --> B["lift the deeper node up to the same depth"]
    B --> C{"u == v?"}
    C -- yes --> R["answer: u"]
    C -- no --> D["for j from high to 0:<br/>if up[j][u] != up[j][v], jump both"]
    D --> E["answer: parent of u"]

Phase one equalizes depths; phase two jumps both nodes as far as possible without meeting.

Why can you go from the highest j down? Think of it as a binary search on the number of steps. If the ancestors 2^j above are different, the LCA is higher still, so jumping is safe. If they are the same, you overshot (or hit the LCA) so you skip that jump and try a smaller one. This is the same greedy that builds a number from its bits.

A full implementation

The class below builds the table from an edge list (using a stack, not recursion, so deep trees are fine) and offers kth_ancestor, lca and distance. The distance between two nodes follows from the LCA:

TEXT
dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]
Python LCA, k-th ancestor and distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity and trade-offs

Part Time Space
Build the table O(n log n) O(n log n)
k-th ancestor O(log n)
LCA O(log n)
Distance O(log n)

Binary lifting is easy to write and also works with a changing tree that only grows by adding leaves (compute the new leaf's row from its parent in O(log n)). Alternatives for LCA:

  • Euler tour + sparse table: O(n log n) build, O(1) query, because LCA becomes a range minimum over depths. Better when you have millions of queries.
  • Heavy-light decomposition: O(n) memory and O(log n) LCA, and it also handles path queries and updates.
  • Offline Tarjan LCA with union-find: all queries known in advance, nearly O(n + q).

A related use: if each jump also stores an aggregate (the maximum edge weight on the path, a sum, a gcd), then up[j][v] plus best[j][v] lets you combine along the same O(log n) jumps. That answers "max edge on the path between u and v" without a segment tree.

For huge trees in Python, store each row in a list of ints or an array('i') to cut memory, or switch to an Euler-tour approach that needs only about 2n entries and a sparse table over them.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is up[j][v] in binary lifting?

    Row j stores the ancestor 2^j steps up. Row 0 is the parent, and row j is row j-1 applied twice.
  2. 2. How do you compute the 13th ancestor (13 = 1101 in binary)?

    13 = 8 + 4 + 1, so you take the 8-jump, the 4-jump and the 1-jump.
  3. 3. In the second phase of the LCA algorithm, when do you jump both nodes?

    If the 2^j-th ancestors differ, they are still strictly below the LCA, so both nodes can safely jump. If they are equal, the jump would reach or pass the LCA.
  4. 4. How do you compute the number of edges between u and v once you know their LCA?

    The path goes up from u to the LCA and down to v, so the two depth gaps add up.
  5. 5. What is the memory cost of the table for n nodes?

    There are about log2(n) rows with n entries each.

Summary

  • Binary lifting stores each node's ancestors 1, 2, 4, 8, ... steps up: up[j][v] = up[j-1][up[j-1][v]].
  • The table takes O(n log n) time and space to build.
  • The k-th ancestor needs one jump per set bit of k: O(log n).
  • LCA: first lift the deeper node to the same depth, then jump both from high j to low j whenever the ancestors differ, and finish with one step to the parent.
  • dist(u, v) = depth[u] + depth[v] - 2 * depth[lca].
  • For millions of queries, an Euler tour with a sparse table answers LCA in O(1).

Next: Cartesian Trees