LeetCode 1483-Kth Ancestor of a Tree Node | Binary Lifting

I was once again doing what I always do while solving tree problems playing around comfortably with brute force and convincing myself that maybe this time the constraints would be forgiving.

They were not.

The problem looked harmless. Every node in the tree only knew its direct parent, and queries kept asking things like:

“What is the kth ancestor of this node?”

Meaning:

If we keep moving upward k times, where do we finally end up?

At first, the solution felt painfully obvious. If a node wants to know all the ancestors above it, why not simply store the entire path to the top beforehand?

Honestly, my brain was fully satisfied with this idea for a while.

Then memory exploded( got MLE ).

Somewhere between crashing solutions, fading confidence, and having no idea how to optimize memory, I stumbled upon a Binary Lifting blog on CP blogs but the intuition was still missing. Honestly, I could not even understand what the phrase “Binary Lifting” was supposed to mean. It sounded less like an algorithm and more like a gym workout designed by mathematicians.

To understand that shift properly, imagine a mountain kingdom.

At the very top of the mountain lives the king in village 0. Every other village below has exactly one upward road leading toward its parent village. Some villages are directly connected to the king, while others are buried deep down the mountain.

Something like this:

0 <- 1 <- 2 <- 3 <- 4 <- 5 <- 6

Now imagine villagers constantly arriving at the royal office asking questions like:

“What is the 4th ancestor of village 6?”

“What is the 13th ancestor of village 25?”

“If I keep moving upward, where will I end after k steps?”

The first villager assigned to solve this problem is extremely hardworking.

Possibly too hardworking.

He decides that for every village, he will write the complete upward path to the king inside a notebook.

For village 6, he stores:

[5,4,3,2,1,0]

For village 5:

[4,3,2,1,0]

For village 4:

[3,2,1,0]

Now answering queries becomes incredibly easy. If someone asks for the 3rd ancestor of village 6, he simply opens the notebook and checks the 3rd entry.

Fast answer.

Simple logic.

No complicated tricks.

And honestly, this solution feels correct because it is correct. The problem only appears when the mountain becomes enormous. Imagine the villages form one gigantic chain stretching downward forever:

0 <- 1 <- 2 <- 3 <- 4 <- ...

Now the notebooks start becoming ridiculous.

Village 1 stores 1 ancestor.

Village 100 stores 100 ancestors.

Village 10000 stores 10000 ancestors.

And eventually some poor villager is basically storing the entire mountain inside a single notebook. At this point, the problem is no longer about finding ancestors correctly. The brute force already does that perfectly. The real issue is that we are repeatedly storing almost the same information again and again.

For example:

Village 1000:
[999,998,997,996,...]

Village 1001:
[1000,999,998,997,...]

Most of the path overlaps.

We are consuming massive amounts of memory simply because we only know one way to move upward: 1 step at a time

And this is where the second villager enters the story. Unlike the first villager, this one is lazy in a very intelligent way. He watches the growing mountain of notebooks and asks a very small but dangerous question:

“Why are we storing every single step?”

That single question completely changes the direction of thinking.

Suppose someone asks:

“What is the 13th ancestor?”

The first villager thinks entirely in terms of movement: 1 step 1 step 1 step ... 13 times

But the second villager notices something strange hidden inside the number itself. 13 = 8 + 4 + 1

Then:

19 = 16 + 2 + 1

Then:

40 = 32 + 8

Every number can already be broken into powers of 2. And that observation quietly becomes the real beginning of Binary Lifting. Because suddenly the villager realizes something important. If we somehow know how to jump:

1 step
2 steps
4 steps
8 steps
16 steps
...

then we can combine those jumps together to recreate any upward movement.

That is the core intuition behind Binary Lifting.

We are not losing information by storing less.

We are storing movement in a compressed form.

Instead of remembering every single ancestor individually, we only remember a few carefully chosen jump checkpoints. Then larger movements are rebuilt by combining those smaller jumps together.

The beautiful part is that the “magic” is not hidden inside the tree.

It is hidden inside the number itself.

For example:

13 = 1101 (binary)

Now read the bits from right to left:

1 -> use 1 jump
0 -> skip 2 jump
1 -> use 4 jump
1 -> use 8 jump

So the binary representation itself secretly tells us which jumps are needed.

That means if we already know how to perform jumps of size 1, 2, 4, 8..., then we can reconstruct the exact answer efficiently.

Now comes the deeper question.

Why does this actually work?

Suppose someone asks for the 13th ancestor of village 15.

The villager sees:

13 = 8 + 4 + 1

So instead of walking upward 13 separate times manually, he performs:

15 --8 jumps--> 7
7  --4 jumps--> 3
3  --1 jump--> 2

And somehow this still gives the exact same answer as normal upward traversal.

Why?

Because every jump already represents a completely valid upward movement.

An 8-jump literally means:

“Move exactly 8 ancestors upward.”

Then the 4-jump continues from there, and the 1-jump finishes the remaining movement. The movements stack perfectly because ancestor movement is cumulative. Moving upward 8 times and then 4 more times is exactly the same as moving upward 12 times continuously.

We are not approximating the path.

We are reconstructing the exact same journey using larger reusable building blocks. And this is where Binary Lifting stops feeling like a trick and starts feeling natural.

But there is still one final piece missing.

How does the villager even know where an 8-jump lands?

Does he manually compute all 8 moves every time?

No.

And this is probably the smartest observation in the entire technique.

Suppose we already know the 4-jump ancestor of every village.

Then suddenly the 8-jump ancestor becomes easy.

Because:

8 jump = 4 jump + 4 jump

Meaning:

First perform a 4-jump.

Wherever you land, perform another 4-jump from there.

Done.

Similarly:

4 jump = 2 jump + 2 jump

And:

2 jump = 1 jump + 1 jump

Larger jumps are recursively built using smaller jumps that were already computed earlier.

That recursive structure is the real heart of Binary Lifting.

Eventually this leads to the famous table:

ancestor[node][jumpPower]

Here:

• node represents the current node or village.
• jumpPower represents the power of 2 jump size.

So:

ancestor[node][0]

stores the 1 jump ancestor.

ancestor[node][1]

stores the 2 jump ancestor.

ancestor[node][2]

stores the 4 jump ancestor.

And larger jumps are built using already known smaller jumps.

That is exactly what this formula does:

ancestor[node][jumpPower]
=
ancestor[
    ancestor[node][jumpPower - 1]
][jumpPower - 1];

At first this formula looks scary.

But the intuition is simple.

To calculate an 8 jump, we first do a 4 jump. Wherever that lands, we again perform another 4 jump.

Together:

4 jump + 4 jump = 8 jump

And the same idea recursively builds the entire table. Now once the table is ready, retrieving the answer becomes surprisingly elegant. We simply look at the binary representation of k.

For example: 13 = 1101

Then we check every bit one by one. If a bit is ON, it means that jump is needed.

That is exactly what this line checks:

if ((k >> jumpPower) & 1)

Here:

• k is the ancestor distance we want.
• jumpPower is the current power of 2 we are checking.

Suppose: 13 = 1101

If: jumpPower = 0 then: 13 >> 0 = 1101 The last bit is 1.

So we use the 1 jump.

If: jumpPower = 1 then: 13 >> 1 = 110 Last bit becomes 0.

So we skip the 2 jump.

If: jumpPower = 2 then: 13 >> 2 = 11 The last bit is 1.

So we use the 4 jump.

And similarly we also use the 8 jump.

That is how the binary number itself guides the movement.

The bits decide which jumps are needed. The ancestor table tells us where those jumps land. And together they reconstruct the exact same path efficiently. What initially looked like magic teleportation is actually just carefully reused movement.

Less storage. Same answer. Smarter movement.

And honestly, that is what makes Binary Lifting such a beautiful idea. It is not really about trees . It is about recognizing repeated work hidden inside movement itself. The brute force solution already knew where to go. Binary Lifting simply learned how to travel there intelligently.

Useful Links

If you want to explore Binary Lifting further, these resources helped me understand the technique from different perspectives:

CP-Algorithms — Binary Lifting for Lowest Common Ancestor USACO Guide —** ***Binary Jumping / Binary Lifting *LeetCode Problem: 1483. Kth Ancestor of a Tree Node My Brute Force & Optimized Binary Lifting Solution

Not every concept clicks instantly. Sometimes understanding arrives gently, after enough confusion and curiosity.