Back to Data Structures

Doubling Technique

October 18, 2026 Wasil Zafar 19 min read

Concepts, invariants, and Python, C++, and Java implementations of Doubling Technique

Table of Contents

  1. Why Doubling Technique Matters
  2. Core Concepts and Terminology
  3. How Doubling Technique Works, Step by Step
  4. Worked Example with a Full Trace
  5. Implementation in Python, C++, and Java
  6. Complexity, Correctness, and Invariants
  7. Variants, Pitfalls, and Optimizations
  8. Practice Problems and Real-World Use

Why Doubling Technique Matters

In pointer-based systems, trees, and functional graphs, navigating $K$ steps sequentially from a node requires traversing edges one by one in $O(K)$ time. When an application performs millions of queries—such as looking up the $K$-th ancestor of a node in a file system directory tree, finding the lowest common ancestor (LCA) of two network switches, or simulating state transitions over millions of time steps—naive linear traversal creates an insurmountable performance bottleneck.

The Doubling Technique (commonly known as Binary Lifting) overcomes this linear limitation by precomputing power-of-two jump targets. By storing $2^0, 2^1, 2^2, \dots, 2^j$ step pointers for every node, any step count $K$ can be decomposed into its binary representation $\sum b_i 2^i$. Jumping across these precomputed powers of two reduces $O(K)$ sequential traversals to $O(\log K)$ pointer hops. Precomputing this table requires $O(N \log K_{max})$ time and space, enabling instant $O(\log K)$ queries across massive structures.

The Doubling Technique precomputes jump targets at exponentially increasing intervals ($2^0, 2^1, 2^2, \dots$) to evaluate $K$-step transitions in $O(\log K)$ time. By expressing any integer $K$ as a sum of powers of two, long traversals are replaced with at most $\lfloor \log_2 K \rfloor + 1$ pointer operations.

Core Concepts and Terminology

The foundational element of the doubling technique is the binary lifting table, traditionally denoted as up[u][j] (or jump[u][j]).

  • Base Pointer (up[u][0]): The direct successor or immediate parent of node $u$ (a jump of $2^0 = 1$ step).
  • Recurrence Relation: A jump of length $2^j$ is composed of two consecutive jumps of length $2^{j-1}$:

$$up[u][j] = up[\,up[u][j-1]\,][j-1]$$

  • Binary Step Decomposition: To jump $K$ steps from node $u$, iterate through the bit positions of $K$ from highest to lowest. If the $j$-th bit of $K$ is set ($K \ \& \ (1 \ll j) \ne 0$), update $u \leftarrow up[u][j]$.
A doubling table built level by level beside a query that decomposes thirteen steps into powers of two Each level of the jump table composes two jumps of the level below, so every column doubles the reach. Any step count such as thirteen splits into eight plus four plus one, and each set bit costs a single pointer hop. Every 2^j jump is two glued 2^(j−1) jumps LEVEL-BY-LEVEL TABLE DECOMPOSE K = 13 up[u][0] = parent(u) — a 1-step jump up[u][1] = up[up[u][0]][0] — a 2-step jump up[u][2] = up[up[u][1]][1] — a 4-step jump up[u][3] = up[up[u][2]][2] — an 8-step jump Each column is built from the column before it, so LOG columns cover every jump up to the root. Build once in O(N log N), hop in O(log K). K = 13 = 8 + 4 + 1, binary 1101 bit 3 set: u ← up[u][3] (8 steps) bit 2 set: u ← up[u][2] (4 steps) bit 0 set: u ← up[u][0] (1 step) At most one hop per level; clear bits are skipped for free, never one hop per edge. Thirteen steps cost 3 pointer hops. The recurrence up[u][j] = up[up[u][j−1]][j−1] doubles the reach of every column. A K-step query walks the set bits of K, one table lookup per set bit.
TermDefinitionRole in AlgorithmExample
up[u][j]The node reached after taking $2^j$ steps upward/forward from node $u$.Core binary lifting lookup table.up[5][2] is the $4$-th ancestor of node $5$.
LOG BoundaryUpper bound on exponent $j$, where $2^{\text{LOG}-1} \ge N$.Dictates table column dimension $\lceil \log_2 N \rceil$.For $N = 100,000$, $\text{LOG} = 17$.
Binary DecompositionRepresenting step count $K$ as a sum of distinct powers of two.Breaks $K$ steps into at most $\log_2 K$ pointer lookups.$K = 13 = 2^3 + 2^2 + 2^0$ ($8 + 4 + 1$).
Lowest Common Ancestor (LCA)Deepest node that is an ancestor of both node $u$ and node $v$.Computed by lifting $u$ and $v$ simultaneously.$\text{LCA}(3, 5) = 0$ in a rooted tree.
Functional GraphDirected graph where every node has out-degree equal to $1$.Domain for non-tree doubling (successor graphs).State machine transition graph $f(x)$.

How Doubling Technique Works, Step by Step

Execution proceeds in two distinct phases: Table Precomputation and Query Processing.

Phase 1: Precomputation ($O(N \log N)$)

  1. Initialize up[u][0] with direct parent/successor pointers for all nodes $u \in [0, N-1]$.
  2. For exponent level $j = 1$ up to $\text{LOG}-1$: For each node $u$: compute up[u][j] = up[up[u][j-1]][j-1]. If up[u][j-1] is out-of-bounds or root, set up[u][j] to root or null.

Phase 2: Query Execution ($O(\log K)$)

To find the $K$-th ancestor/successor of node $u$:

  1. For $j = \text{LOG}-1$ down to $0$: If bit $j$ of $K$ is set ($K \ \& \ (1 \ll j)$): Update $u \leftarrow \text{up}[u][j]$.
  1. Return $u$.
Step-by-Step Resolution: Finding K = 5th Ancestor of Node 5 The step count five decomposes into four plus one. The query scans bit levels from high to low, performs one four-step table jump, skips a clear bit, performs a one-step jump clamped at the root, and returns node zero. Step-by-Step Resolution: Finding K = 5th Ancestor of Node 5 QUERY SETUP JUMP SEQUENCE Start: u = 5, K = 5 steps requested LOG = 4, scan bits j = 3 down to 0 K = 5 in binary is 101 (bits 2 and 0 set) Clear bits 3 and 1 are skipped for free No edge walking is ever performed; only precomputed table lookups occur. Five edge walks collapse into 2 hops. j = 2 set: u ← up[5][2] = 0 (4 steps) j = 1 clear: u stays at node 0 j = 0 set: u ← up[0][0] = 0 (1 step) Return node 0 as the 5th ancestor Root entries point to themselves, so oversized jumps clamp safely at the top. Two lookups answer a 5-step query. Decomposition: K = 5 = 2^2 + 2^0 (4 steps + 1 step) Each set bit becomes one table lookup; clear bits cost nothing.
Doubling Technique control flow
flowchart TD
A[Start: Input Node u, Jump Count K] --> B[Initialize j = LOG - 1]
B --> C{j >= 0 ?}
C -- Yes --> D{Is j-th bit of K set? K & 1<<j}
D -- Yes --> E[u = up[u][j]]
D -- No --> F[Decrement j = j - 1]
E --> F
F --> C
C -- No --> G[Return Destination Node u]

Worked Example with a Full Trace

Consider a tree of $N = 6$ nodes with root 0 and direct parent pointers: parent = [0, 0, 0, 1, 2, 2] (Depths: node 0 depth 0; nodes 1,2 depth 1; nodes 3,4,5 depth 2).

Precomputed Table up[u][j] ($\text{LOG} = 4$)

Node $u$Depthup[u][0] ($2^0=1$)up[u][1] ($2^1=2$)up[u][2] ($2^2=4$)up[u][3] ($2^3=8$)
000000
110000
210000
321000
422000
522000
Trace: Finding Lowest Common Ancestor LCA(3, 5) A six node tree rooted at node zero with node three and node five highlighted. Both probes sit at depth two, the two-step lifts are equal and rejected, the one-step lifts differ so both probes jump to nodes one and two, and the answer is the parent of node one, node zero. Trace: Finding Lowest Common Ancestor LCA(3, 5) THE TREE, ROOT 0 0 1 2 3 4 5 LCA TRACE: LCA(3, 5) 1. depth[3] = 2, depth[5] = 2 → no lift 2. j = 1: up[3][1] = 0 = up[5][1], stay 3. j = 0: up[3][0] = 1 ≠ up[5][0] = 2 → jump u = 1, v = 2, one level below the LCA 4. Final LCA = up[1][0] = 0 Equal lifts are rejected so the probes never rise above the lowest common ancestor. Answer: LCA(3, 5) = node 0. Depths are equal, so the search starts with both probes at level 2. Jump only on inequality; the loop stops exactly one level below the LCA.
Worked Example

Trace It by Hand

Scenario: Using the tree above (parent = [0, 0, 0, 1, 2, 2]), trace the execution of get_lca(4, 5).

  1. Depth Check: depth[4] = 2, depth[5] = 2. Both nodes are at equal depth.
  2. Loop $j = 1$ ($2^1 = 2$ steps): up[4][1] = 0, up[5][1] = 0. Both pointers equal 0. Since they match, we do not jump (jumping would overshoot past the LCA).
  3. Loop $j = 0$ ($2^0 = 1$ step): up[4][0] = 2, up[5][0] = 2. Both pointers equal 2. Since they match, we do not jump.
  4. Termination: Return up[4][0] = 2. The lowest common ancestor of nodes 4 and 5 is Node 2.

Implementation in Python, C++, and Java

The complete implementations below build the binary lifting table for a 6-node tree, execute $K$-th ancestor queries, and compute Lowest Common Ancestors (LCA). All three implementations produce identical terminal output.

class BinaryLifting:
    def __init__(self, n, parent, depth):
        self.n = n
        self.LOG = 4
        self.depth = depth
        self.up = [[0] * self.LOG for _ in range(n)]

        for i in range(n):
            self.up[i][0] = parent[i]

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

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

    def get_lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        diff = self.depth[u] - self.depth[v]
        u = self.get_kth_ancestor(u, diff)

        if u == v:
            return u

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

        return self.up[u][0]

if __name__ == "__main__":
    n = 6
    parent = [0, 0, 0, 1, 2, 2]
    depth = [0, 1, 1, 2, 2, 2]

    bl = BinaryLifting(n, parent, depth)

    print(f"1st ancestor of node 5: {bl.get_kth_ancestor(5, 1)}")
    print(f"2nd ancestor of node 5: {bl.get_kth_ancestor(5, 2)}")
    print(f"2nd ancestor of node 3: {bl.get_kth_ancestor(3, 2)}")
    print(f"LCA of node 3 and node 5: {bl.get_lca(3, 5)}")
    print(f"LCA of node 4 and node 5: {bl.get_lca(4, 5)}")

#include <iostream>
#include <vector>
#include <algorithm>

class BinaryLifting {
private:
    int n;
    int LOG;
    std::vector<int> depth;
    std::vector<std::vector<int>> up;

public:
    BinaryLifting(int n, const std::vector<int>& parent, const std::vector<int>& depth)
        : n(n), LOG(4), depth(depth), up(n, std::vector<int>(4, 0)) {

        for (int i = 0; i < n; ++i) {
            up[i][0] = parent[i];
        }

        for (int j = 1; j < LOG; ++j) {
            for (int i = 0; i < n; ++i) {
                up[i][j] = up[up[i][j - 1]][j - 1];
            }
        }
    }

    int getKthAncestor(int node, int k) const {
        for (int j = LOG - 1; j >= 0; --j) {
            if ((k >> j) & 1) {
                node = up[node][j];
            }
        }
        return node;
    }

    int getLCA(int u, int v) const {
        if (depth[u] < depth[v]) {
            std::swap(u, v);
        }

        int diff = depth[u] - depth[v];
        u = getKthAncestor(u, diff);

        if (u == v) {
            return u;
        }

        for (int j = LOG - 1; j >= 0; --j) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        return up[u][0];
    }
};

int main() {
    int n = 6;
    std::vector<int> parent = {0, 0, 0, 1, 2, 2};
    std::vector<int> depth = {0, 1, 1, 2, 2, 2};

    BinaryLifting bl(n, parent, depth);

    std::cout << "1st ancestor of node 5: " << bl.getKthAncestor(5, 1) << "\n";
    std::cout << "2nd ancestor of node 5: " << bl.getKthAncestor(5, 2) << "\n";
    std::cout << "2nd ancestor of node 3: " << bl.getKthAncestor(3, 2) << "\n";
    std::cout << "LCA of node 3 and node 5: " << bl.getLCA(3, 5) << "\n";
    std::cout << "LCA of node 4 and node 5: " << bl.getLCA(4, 5) << "\n";

    return 0;
}

public class Main {
    static class BinaryLifting {
        private final int n;
        private final int LOG = 4;
        private final int[] depth;
        private final int[][] up;

        public BinaryLifting(int n, int[] parent, int[] depth) {
            this.n = n;
            this.depth = depth;
            this.up = new int[n][LOG];

            for (int i = 0; i < n; i++) {
                up[i][0] = parent[i];
            }

            for (int j = 1; j < LOG; j++) {
                for (int i = 0; i < n; i++) {
                    up[i][j] = up[up[i][j - 1]][j - 1];
                }
            }
        }

        public int getKthAncestor(int node, int k) {
            for (int j = LOG - 1; j >= 0; j--) {
                if (((k >> j) & 1) == 1) {
                    node = up[node][j];
                }
            }
            return node;
        }

        public int getLCA(int u, int v) {
            if (depth[u] < depth[v]) {
                int temp = u;
                u = v;
                v = temp;
            }

            int diff = depth[u] - depth[v];
            u = getKthAncestor(u, diff);

            if (u == v) {
                return u;
            }

            for (int j = LOG - 1; j >= 0; j--) {
                if (up[u][j] != up[v][j]) {
                    u = up[u][j];
                    v = up[v][j];
                }
            }

            return up[u][0];
        }
    }

    public static void main(String[] args) {
        int n = 6;
        int[] parent = {0, 0, 0, 1, 2, 2};
        int[] depth = {0, 1, 1, 2, 2, 2};

        BinaryLifting bl = new BinaryLifting(n, parent, depth);

        System.out.println("1st ancestor of node 5: " + bl.getKthAncestor(5, 1));
        System.out.println("2nd ancestor of node 5: " + bl.getKthAncestor(5, 2));
        System.out.println("2nd ancestor of node 3: " + bl.getKthAncestor(3, 2));
        System.out.println("LCA of node 3 and node 5: " + bl.getLCA(3, 5));
        System.out.println("LCA of node 4 and node 5: " + bl.getLCA(4, 5));
    }
}

Complexity, Correctness, and Invariants

Analyzing doubling algorithm complexity highlights its efficiency for multi-query operations.

Operation / StructurePrecomputation TimeQuery TimeAuxiliary SpaceKey Trade-offs
Doubling Technique$O(N \log N)$$O(\log K)$$O(N \log N)$Optimal general-purpose approach for trees and functional graphs.
Linear Pointer Hopping$O(N)$$O(K)$$O(N)$Minimal memory footprint, but unacceptably slow for large $K$.
Euler Tour + RMQ (Sparse Table)$O(N \log N)$$O(1)$$O(N \log N)$Instant LCA query time, but limited to static trees (cannot query $K$-th ancestor directly).
Heavy-Light Decomposition (HLD)$O(N)$$O(\log^2 N)$$O(N)$Supports path updates/queries; higher implementation complexity.

Binary Lifting Invariant: For any node $u$ and exponent $j \ge 1$, the table entry up[u][j] equals the node reached by taking $2^{j-1}$ steps from up[u][j-1]. Consequently, applying the sequence of jumps corresponding to the set bits of $K$ correctly reaches the exact $K$-step ancestor.

Variants, Pitfalls, and Optimizations

Common Variants

  1. Tree Path Aggregates: Storing $2^j$-step path minimums, maximums, or sums alongside node pointers (min_edge[u][j] = min(min_edge[u][j-1], min_edge[up[u][j-1]][j-1])).
  2. Functional Graphs (Cycles & Tails): Finding state after $K$ steps in graphs where every vertex has out-degree $1$.

Critical Pitfalls

Jumping on equal lifted pointers overshoots the lowest common ancestor For the pair node four and node five whose true lowest common ancestor is node two, the correct rule lifts only when the lifted pointers differ and returns node two. The buggy rule lifts when the pointers are equal, merges both probes at the root, and wrongly returns node zero. Equal pointers must block the jump, not trigger it CORRECT: JUMP IF DIFFERENT BUG: JUMP IF EQUAL Lift only when up[u][j] ≠ up[v][j] LCA(4, 5): j = 1 lifts both to 0, equal, stay j = 0: up[4][0] = 2 = up[5][0], stay Loop ends with u = 4, v = 5 untouched Both probes halt exactly one level below the lowest common ancestor. Return up[4][0] = 2, the true LCA. Lift whenever up[u][j] = up[v][j] LCA(4, 5): j = 1 lifts both to 0, equal → jump Probes merge at the root: u = v = 0 Returns node 0, but the true LCA is node 2 Any common ancestor can be returned, not necessarily the lowest one. Overshoot: the answer climbs above the LCA. Implementation Pitfall: Equal Pointer Jumping in LCA Lift on inequality so both probes stop just below the answer; equality means overshoot.

Top Implementation Pitfalls:

  1. Overshooting LCA: When searching for LCA, jumping when up[u][j] == up[v][j] overshoots to higher common ancestors. You must jump only when up[u][j] != up[v][j] so execution halts exactly one level below the LCA.
  2. Insufficient LOG Size: Defining $\text{LOG}$ too small (e.g., $\text{LOG} = 16$ for $N = 100,000$) prevents jumps beyond $2^{15} = 32,768$, causing out-of-bounds queries to fail. Always ensure $2^{\text{LOG}-1} \ge N$.
  3. Uninitialized Boundary Values: Failing to point up[root][j] to root (or a designated sentinel node -1) leads to null pointer dereferences or infinite loops when $K$ exceeds the height of the tree.

Practice Problems and Real-World Use

The doubling technique is deployed in competitive programming, file system hierarchies, and distributed routing protocols.

Problem / SystemApplicationDifficulty
LeetCode 1483Design Underground $K$-th Ancestor lookup data structure.Medium
Codeforces 1304E1-to-N shortest path queries on trees with added shortcuts using LCA.Hard
CSES Company Queries I & IIDirect applications of $K$-th ancestor and LCA via binary lifting.Easy / Medium
Unix Virtual File System (VFS)Resolving absolute path lookup requests across nested directory inodes.Real-World System
BGP Router Path SelectionComputing lowest common autonomous system (AS) transit hubs in routing tables.Real-World System
Distributed Hash Tables (Chord)Finger tables precompute exponential node jumps ($2^i$) across circular ID spaces.Real-World System