Guide to Binary Lifting & LCA

So, Everything starts when i was doing a Problem Of The Day on Leetcode — Specifically **3559. Number of Ways to Assign Edge Weights II. Due to this problem i was introduced to a famous Optimization Technique in C.P. World — Binary Lifting**

It happens to all of us, especially when dealing with trees. Trees are beautiful data structures, but traversing them naively (like using standard DFS or BFS) every single time a query asks about a path takes O(N) time. If you have Q queries, your runtime balloons to an painful O(Q N)**. When both your tree size and queries scale up to 10⁵, you’re looking at nearly 10¹⁰*** operations. That completely breaks the standard 1-second limit.

The Core Idea: Teleporting up the Tree :

To get an intuition for Binary Lifting, think about how we count in binary (base-2). Every single integer can be uniquely broken down into a sum of powers of 2.

Let’s say you’re standing at a node deep in a tree, and you want to jump to its 13th ancestor. If you climb up one branch at a time, it will take you 13 manual steps.

Binary lifting changes the game rules completely. Because 13 = 8 + 4 + 1 (or 1101 in binary), you can cross that exact same distance in just three giant leaps:

• We Take a massive leap of 8 levels up to an intermediate ancestor.
• From there, take a secondary leap of 4 levels up.
• Take one final step of 1 level up to land exactly on your target.

The Number 2 is very Special. We can represent any number in this Universe using power of 2. That’s why this technique is named as Binary Lifting.

Building the Engine with Dynamic Programming :

To keep track of these exponential leaps, we use a 2D dynamic programming table usually called up or ancestorTable.

The Rule: up[node][j] stores the 2^j-th ancestor directly above node.

To find your **2^j-th ancestor, you simply jump up by** 2^j-1 levels, see where you land, and then make another jump of ***2^j-1*** levels from that intermediate node. This gives us our clean DP recurrence relation:

Recurrence Relation for Efficient Jumping : up[up[node][j-1]][j-1].

Better to remember this realtion.

The Two Main Superpowers of Binary Lifting

Once your table is built, Binary Lifting grants you two major capabilities:

1. Finding the K-th Ancestor in O(log K)

If you need to find the K-th ancestor of a node, you just look at the binary bits of K. For every bit j that is turned on (equal to 1), you perform the precomputed jump of 2^j.

int getKthAncestor(int node, int k, int cols, vector<vector<int>>& up) {
    for (int j = 0; j < cols; j++) {
        if (k & (1 << j)) { // Is the j-th bit of k set?
            node = up[node][j];
            if (node == -1) break; // We went past the root node
        }
    }
    return node;
}

2. Finding the Lowest Common Ancestor (LCA)

The Lowest Common Ancestor (LCA) of two nodes is the deepest shared parent node where their paths merge. Binary Lifting handles this query in two simple phases:

• Equalize the Levels: If the two nodes are at different depths, find the deeper one and lift it up (using the K-th ancestor logic) until its depth matches the shallower node. If it lands directly on top of the other node, then that node is their common ancestor, and we can stop right there.
• Climb Together: If they are on the same level but still different nodes, we step down through our jump powers from largest (cols - 1) down to 0. If their ancestors at a certain jump are different (up[u][j] != up[v][j]), it means they haven't met yet. We take the jump, lifting both nodes up simultaneously.

By the end of this countdown loop, the nodes will sit exactly one level right below their shared intersection point. Therefore, up[u][0] is the final LCA!

Code Blueprint: The Full C++ Template

Here is a clean, template to implement Binary Lifting from scratch.

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

    // 1: standard DFS to find depths and immediate parents (2^0 ancestors)
    void dfs(int node, int parent, const vector<vector<int>>& adj) {
        up[node][0] = parent;
        for (int ngbr : adj[node]) {
            if (ngbr != parent) {
                depth[ngbr] = depth[node] + 1;
                dfs(ngbr, node, adj);
            }
        }
    }

    // 2. compute the remaining columns of the DP table
    void buildTable() {
        for (int j = 1; j < cols; j++) {
            for (int node = 0; node < n; node++) {
                if (up[node][j - 1] != -1) {
                    up[node][j] = up[up[node][j - 1]][j - 1];
                }
            }
        }
    }

public:
    BinaryLifting(int numNodes, int root, const vector<vector<int>>& adj) {
        n = numNodes;
        cols = log2(n) + 1;
        up.resize(n, vector<int>(cols, -1));
        depth.resize(n, 0);

        dfs(root, -1, adj);
        buildTable();
    }

    int getKthAncestor(int node, int k) {
        for (int j = 0; j < cols; j++) {
            if (k & (1 << j)) {
                node = up[node][j];
                if (node == -1) break;
            }
        }
        return node;
    }

    int getLCA(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v); // keep 'u' as the deeper node

        // Step 1: bring both nodes to the same depth level
        int k = depth[u] - depth[v];
        u = getKthAncestor(u, k);

        if (u == v) return u; // Early exit if one is the ancestor of the other

        // Step 2: climb together synchronously
        for (int j = cols - 1; j >= 0; j--) {
            if (up[u][j] != -1 && up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        return up[u][0]; // the immediate parent is the LCA
    }

    int getDistance(int u, int v) {
        int lca = getLCA(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
};

Why This Approach is a Game-Changer

By upgrading your codebase to use Binary Lifting, the efficiency footprint of your tree applications transforms completely:

1. Time Complexity:

• Preprocessing: O(Nlog N) to run the initial DFS and build out the lookup matrix.
• Per Query: A incredibly fast O(log N) to find any LCA or K-th ancestor.

2. Space Complexity: O(N log N) memory overhead to hold your 2D table in memory.

Wrapping Up

Binary Lifting is a core foundational pattern for advanced tree problems. By moving away from step-by-step linear loops and embracing binary-based exponential leaps, you can evaluate complex tree path attributes — like distances, path maximums, or node parents — in fractions of a millisecond.

The next time you see a tree problem tracking node paths or ancestors under heavy query constraints, skip the basic loops and implement a binary lifting table instead!