Binary Lifting: My First Time Applying DP on Binary Trees

Binary lifting is causing a revolution in tree-based computations, offering a clever way to handle complex tree queries efficiently. This dynamic programming approach allows for quick navigation through tree structures, making it a game-changer for various tree-related problems.

Fundamental Principles

At its core, binary lifting is all about precomputing ancestors of nodes in a tree. It creates a jump table that lets us zip up the tree by powers of 2, which is pretty neat. This technique involves maintaining an array of parent pointers, where each entry represents an ancestor that's a power of 2 steps away from the current node.

OK now suppose you are looking for the Kth ancestor of a node what are you going to solve it ?

Every number K can be represented in binary form. For example, the number 13 in binary is 1101, which is 1×2^3+1×2^2+1×2^0

"You didn’t think about it, did you? I knew it...

but have you had your ‘AHA’ moment 💡 yet?"

Now In the context of binary lifting, this means that any jump of length K can be broken down into jumps of lengths that are powers of two.

Let's say we want to find the 100th ancestor of a node. Instead of taking 100 tedious steps up the tree, binary lifting breaks it down into bigger jumps:

1. it jumps to the 64th ancestor (2^6)

2. it hops to the 32nd ancestor (2^5)

3. t takes a small leap to the 4th ancestor (2^2)

This clever approach mirrors the binary representation of 100 (1100100 in binary), making the process super efficient.

But wait you said you are using dp?

Building the Jump Table

To make this magic happen, we need to build a special table up. Here's how it works:

1. We start by noting down each node's immediate parent

2. Then, we use a cool recursive formula to fill in the rest of the table

3. For each node, we calculate its 2nd, 4th, 8th, 16th (and so on) ancestors

The recurrence formula for the up array is derived from the idea of repeatedly halving the distance to the ancestor 🪜

up[u][j]=up[up[u][j−1]][j−1]

Think about it 🤔 to find the 2^j-th ancestor of node u, we can use the 2^(j-1)-th ancestor of the 2^(j-1)-th ancestor of u. (2^k = 2^(k-1) +2^(k-1) ).

This ensures that we have enough precomputed ancestors to cover all possible jumps needed to lift any node up to the root of the tree.

In other words, 2^k must be less than or equal to N, which gives k≤log⁡2(N).

Time Complexity

The preprocessing step involves a DFS traversal to initialize the first ancestor (up[node][0]) and calculate the depth of each node, which takes O(N). Filling in the rest of the binary lifting table requires O(Nlog⁡N) time because for each of the N nodes, we fill up to logN ancestors.

Inspired by 1483. Kth Ancestor of a Tree Node

Solution in Java

class TreeAncestor {

    int dp[][];
    int m;
    int n;

    public TreeAncestor(int n, int[] parent) {
        this.n = n;
        this.m = (int) (Math.log(n) / Math.log(2)) + 1;
        dp = new int[m][n];
        for(int i[] : dp) {
            Arrays.fill(i, -1);
        }

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0) {
                    dp[i][j] = parent[j];
                }
                else {
                    if(dp[i - 1][j] == -1) dp[i][j] = -1;
                    else dp[i][j] = dp[i - 1][dp[i - 1][j]];
                }
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        int row = 0;
        while(k > 0) {
            if((k & 1) == 1) {
                if(node == -1) return -1;
                node = dp[row][node];
            }
            k >>= 1;
            row++;
        }
        return node;
    }
}

FAQs

Q: Could you explain what binary lifting is?

Binary lifting is a technique where the 2^k-th ancestor of each node is precomputed for various values of k and stored in a table. This allows for quick and efficient retrieval of the k-th ancestor for any node when needed.

Q: What is the time complexity associated with binary lifting?

The time complexity for binary lifting, specifically when finding the Lowest Common Ancestor (LCA) in binary trees is O(logN) in the worst, average, and best cases, where n is the number of nodes. Additionally, the time and auxiliary space required for precomputing or preprocessing in binary lifting is O(N*logN).

Thanks for sticking with me through this deep dive! 🚀

If you’ve got more questions or just want to chat about it, drop me a line. I’m all ears!

HappyCoding you all !