What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 187 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

19. Binary Lifting: Kth Ancestor of a Tree Node (LC 1483) • Invariant Proof & Speed-Run

Theory Context•Depth-First Search (DFS)

HardLC 1483

Kth Ancestor of a Tree Node (LeetCode 1483)

You will see how storing every node's 1st, 2nd, 4th, 8th, ... ancestor turns any k-steps-up question into one jump per set bit of k.

Target Frequency:GoogleAmazon

A tree has n nodes named 0 to n - 1, and node 0 is its root. You get it as a list parent: parent[i] is the node directly above node i, and parent[0] = -1 because nothing is above the root.

Going up from a node one edge at a time, the first node you reach is its 1st ancestor (its parent), the next one its 2nd ancestor, and so on. Write a class TreeAncestor:

TreeAncestor(n, parent) receives the tree once.
getKthAncestor(node, k) returns the k-th ancestor of node, or -1 when fewer than k nodes lie above node.

The same tree answers up to 5 * 10⁴ questions.

Worked Examples

Example 1

Input:

["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]

Output:[null, 1, 0, -1]

Explanation: Node 0 is the root, nodes 1 and 2 hang under it, 3 and 4 under 1, and 5 and 6 under 2. One step up from 3 is 1. Two steps up from 5 are 2, then 0. From 6, the path up is 2, then 0, and then nothing: 6 has only two ancestors, so the 3rd one does not exist.

⚖️Formal Constraints & Bounds

1 <= k <= n <= 5 * 10⁴
parent.length == n
parent[0] == -1
0 <= parent[i] < n for every 0 < i < n, and the parents form one tree rooted at node 0.
0 <= node < n
At most 5 * 10⁴ calls are made to getKthAncestor.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Any number of steps is a sum of powers of two, and a jump of 2^j is two jumps of 2^(j-1). So store every node's 2^j-th ancestor for each j once, then answer each question with one jump per set bit of k, keeping -1 as -1 all the way.

Real-World Scenario & Production Applications

Org charts, file systems, version histories and category trees all ask "what is k levels above this?" again and again: the manager k levels up, the folder k levels up, the commit k steps back. When the same tree answers many such questions, storing the power-of-two jumps once makes each question a handful of lookups instead of a long walk.

Step-by-Step Execution Trace Table

Example 1, parent = [-1, 0, 0, 1, 1, 2, 2], so self.LOG = (7).bit_length() = 3. The constructor builds three levels:

Level	Meaning	Row (node 0 to 6)	How
`self.up[0]`	1st ancestor	`[-1, 0, 0, 1, 1, 2, 2]`	the parent list
`self.up[1]`	2nd ancestor	`[-1, -1, -1, 0, 0, 0, 0]`	`prev[prev[v]]`, with `-1` kept for nodes 0, 1, 2
`self.up[2]`	4th ancestor	`[-1, -1, -1, -1, -1, -1, -1]`	the tree is only 2 levels deep

Scroll horizontally to see all columns, or expand to full screen

Then each question jumps once per set bit of k:

Call	`k` in binary	Jumps	Returns
`getKthAncestor(3, 1)`	`1`	`self.up[0][3] = 1`	1
`getKthAncestor(5, 2)`	`10`	`self.up[1][5] = 0`	0
`getKthAncestor(6, 3)`	`11`	`self.up[0][6] = 2`, then `self.up[1][2] = -1`: stop	-1

Scroll horizontally to see all columns, or expand to full screen

Building self.up[1][0] is where the trap sits: prev[0] == -1, and without that check prev[prev[0]] would read prev[-1] = 2, so node 0 would get node 2 as its 2nd ancestor.

Trace Input

["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]

Expected[null, 1, 0, -1]

Example 1, parent = [-1, 0, 0, 1, 1, 2, 2], so self.LOG = (7).bit_length() = 3. The constructor builds three levels:

Level	Meaning	Row (node 0 to 6)	How
`self.up[0]`	1st ancestor	`[-1, 0, 0, 1, 1, 2, 2]`	the parent list
`self.up[1]`	2nd ancestor	`[-1, -1, -1, 0, 0, 0, 0]`	`prev[prev[v]]`, with `-1` kept for nodes 0, 1, 2
`self.up[2]`	4th ancestor	`[-1, -1, -1, -1, -1, -1, -1]`	the tree is only 2 levels deep

Scroll horizontally to see all columns, or expand to full screen

Then each question jumps once per set bit of k:

Call	`k` in binary	Jumps	Returns
`getKthAncestor(3, 1)`	`1`	`self.up[0][3] = 1`	1
`getKthAncestor(5, 2)`	`10`	`self.up[1][5] = 0`	0
`getKthAncestor(6, 3)`	`11`	`self.up[0][6] = 2`, then `self.up[1][2] = -1`: stop	-1

Scroll horizontally to see all columns, or expand to full screen

Building self.up[1][0] is where the trap sits: prev[0] == -1, and without that check prev[prev[0]] would read prev[-1] = 2, so node 0 would get node 2 as its 2nd ancestor.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Store longer jumps once instead of walking one parent at a time: `self.up[j][v]` is the node `2^j` steps above `v`. Any `k` is a sum of powers of two, so a question takes one jump per set bit of `k`.
2	`self.up[0]` is the parent list; level `j` is two jumps of level `j - 1`: `prev[prev[v]]`. In the query, `if k >> j & 1:` then `node = self.up[j][node]`. `self.LOG = max(1, n.bit_length())` levels cover every `k <= n`.
3	The shape: `__init__` sets `self.LOG`, `self.up = [parent[:]]`, then for `j` from 1 appends `[... for v in range(n)]` built from `prev = self.up[j - 1]`. `getKthAncestor` loops `j` over `range(self.LOG)` and returns `node` at the end.
4	The trap: `-1` must stay `-1`. Write `-1 if prev[v] == -1 else prev[prev[v]]`, and `return -1` as soon as `node == -1`: in Python `prev[-1]` is the last node's entry, not an error.

Target: Kth Ancestor of a Tree Node (LeetCode 1483). `k <= n`, so every `k` is written with the bits `0..LOG-1`.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Walking up a tree one parent at a time costs k steps per question, and with 5 * 10⁴ questions on a chain of 5 * 10⁴ nodes that is over a billion steps. Binary Lifting pays once, up front, to store longer jumps: for every node, where 1, 2, 4, 8, ... steps up land. Any k is a sum of powers of two, so a question takes one jump per set bit of k, about log n lookups. The table is built by doubling: a jump of 2^j is a jump of 2^(j-1) from where a jump of 2^(j-1) lands.

🏢 The Analogy: Express Stops on a Metro Line

A metro line has a local train that stops everywhere, an express that skips to every 2nd station, a faster one to every 4th, and so on. To travel 13 stations you ride the 8-station express, then the 4, then the 1: three rides instead of thirteen. The timetable of each express is made from the one below it: two rides of the 4-station express take you exactly where one ride of the 8-station express does. Past the end of the line there is no station, and "no station" must stay "no station" on every faster line too.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

self.LOG = max(1, n.bit_length())
self.up = [parent[:]]
for j in range(1, self.LOG):
    prev = self.up[j - 1]
    self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
 
for j in range(self.LOG):
    if k >> j & 1:
        node = self.up[j][node]
        if node == -1:
            return -1
return node

self.up[j][v] is the node 2^j steps above v. The query reads the bits of k from the lowest; each set bit adds one jump, and jumps add up in any order. The trap sits on both -1 checks: in Python prev[-1] and self.up[j][-1] are not errors but the last node's entries, so a missing ancestor quietly turns into a real node.

💡 Summary

Build self.up level by level, prev[prev[v]] with -1 kept as -1, then answer each question with one jump per set bit of k, stopping at -1. $O(N \log N)$ time and space to build, $O(\log N)$ per question.

Letting -1 index the table: write -1 if prev[v] == -1 else prev[prev[v]] and return as soon as node == -1. Python reads prev[-1] as the last node's entry, so on LeetCode's example tree getKthAncestor(1, 3) would return 2 instead of -1.
Too few levels: self.LOG = max(1, n.bit_length()), not int(math.log2(n)). k can be as large as n, and on a chain of 8 nodes k = 8 needs the level 2³. The level count comes from the largest k (with k up to 10^10, k.bit_length() levels).
Filling the table node by node: build self.up[j] from the whole of self.up[j - 1]. Filling one node's levels at a time reads rows of parents that are not built yet, because parent[i] < i is not promised.
Testing the wrong bit: Test bit j of k with k >> j & 1, not k & j: k & j tests the level number itself, so k = 2 skips the 2-level jump and takes the 4-level one at j = 2.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns many "k steps up" questions into a precomputed table of power-of-two jumps.

Pattern Recognition Signals

The 10-second spot

"getKthAncestor(node, k)", "the same tree answers up to 5 * 10⁴ questions" and "1 <= k <= n <= 5 * 10⁴": the tree never changes, the questions are many, and k can be as long as the whole tree, so walking k parents per question is too slow. That is the signal for Binary Lifting: precompute power-of-two jumps once, then answer each question in about log n jumps.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

self.up[j][v] is the node exactly 2^j steps above v, or -1 when fewer than 2^j nodes lie above it. Level 0 is parent; level j is prev[prev[v]] with prev = self.up[j - 1], kept as -1 when prev[v] == -1. A query walks the bits of k: if k >> j & 1: then node = self.up[j][node], returning -1 as soon as node == -1.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Check prev[v] == -1 before prev[prev[v]], and return as soon as node == -1: Python reads prev[-1] as the last node's entry, so on LeetCode's example tree getKthAncestor(1, 3) would return 2 instead of -1.
self.LOG = max(1, n.bit_length()), not int(math.log2(n)): k can be as large as n, and on a chain of 8 nodes k = 8 needs the level 2³. The level count comes from the largest k: with k up to 10^10, as in Maximize Value of Function in a Ball Passing Game (LC 2836), you need k.bit_length() levels.
Build self.up[j] from the whole of self.up[j - 1], level by level: filling one node's levels at a time reads rows of parents that are not built yet, since parent[i] < i is not promised.
Test bit j of k with k >> j & 1, not k & j: k & j tests the level number itself, so k = 2 skips the 2-level jump and takes the 4-level one at j = 2.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Binary Lifting. The tree is fixed and the questions are many, so I precompute longer jumps once. For every node I store its 1st, 2nd, 4th, 8th ancestor and so on, in a table up where up[j][v] is 2 to the j steps above v. Level 0 is the parent list, and each next level is two jumps of the level before, up[j-1] applied twice, because 2 to the j steps are two jumps of 2 to the j-minus-1 steps each. To answer a question I read k in binary and jump once for each set bit, since the jumps add up in any order. The trap is the root: a missing ancestor is minus one, and in Python indexing with minus one silently reads the last node, so I check for minus one while building and stop as soon as I reach it. Building is O(N log N) time and space, and each question is O(log N).

So: self.up[j][v] holds the node 2^j steps above v; answer with one jump per set bit of k; -1 stays -1.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N log N) to build, O(log N) per query

The constructor copies parent for level 0, then builds self.LOG - 1 more levels, each with one pass over the n nodes that does O(1) work per node: one check and at most two list reads. self.LOG = n.bit_length(), about log2 n + 1, so building is O(N log N). A query runs its loop self.LOG times with O(1) work per turn (a shift, an &, and at most one read and one check), so it is O(log N) no matter how large k is. With Q questions the total is O((N + Q) log N).

SPACE COMPLEXITY

O(N log N)

self.up holds self.LOG lists of n integers: O(N log N). A query keeps only node and j: O(1) extra.

Formal Recurrence Relation

$T = \underbrace{N \cdot \log N}_{\text{build}} + \underbrace{Q \cdot \log N}_{\text{queries}}$

Derivation Progression

Level 0

N

self.up = [parent[:]] copies the parent list.

Levels 1 to LOG - 1

$(\log N) \cdot N$

Each level is one pass over every node: -1 if prev[v] == -1 else prev[prev[v]], O(1) per node.

One query

$\log N$

The loop reads each of self.LOG bits of k once, with at most one table read per bit.

Total

$O((N + Q) \log N)$

Built once, then Q questions of O(log N) each, instead of up to N steps each.

Variable Definitions

$N$

Number of nodes, n

$Q$

Number of getKthAncestor calls

$log N$

self.LOG = n.bit_length(), the number of levels in self.up

Memory Architecture & Bounds

🟣 Call Stack

O(1): no recursion

🔵 Auxiliary Heap

O(N log N): self.up has self.LOG rows of n entries

🟢 Output Space

O(1) per query: one node number

Boundary Best / Worst Cases

Best Case

A query with k a power of two: one table read, but the loop still turns self.LOG times, O(log N)

Average Case

O(log N) per query after an O(N log N) build

Worst Case

A query with every bit of k set: self.LOG jumps, still O(log N)

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: **"getKthAncestor(node, k)"**, **"the same tree answers up to 5 * 10^4 questions"**. A fixed tree, many questions, and k as long as the tree: Binary Lifting, a table of power-of-two jumps built once.

CONSTRAINTS & BOUNDS

$1 \le k \le n \le 5 \times 10^4$ and up to $5 \times 10^4$ questions. Walking k parents per question is up to $2.5 \times 10^9$ steps on a chain; the table has 16 levels of $5 \times 10^4$ entries, $8 \times 10^5$ in all, and each question takes at most 16 jumps.

FAANG PRODUCTION TRAPS & EDGE CASES

The table holds $N \log N$ entries: $8 \times 10^5$ here, but $2 \times 10^7$ for $10^6$ nodes and 20 levels, where compact integer arrays (Python's array module or NumPy) matter more than the algorithm. -1 must stay -1: in Python prev[-1] is the last node, not an error, so a missing guard gives wrong answers instead of a crash. The tree must not change after the build; an insert or a re-parent invalidates every row below it.

Core Algorithmic State Invariants

1. Jumps of Every Power of Two

`self.up[j][v]` is the node `2^j` steps above `v`: level 0 is `parent`, and level `j` is `prev[prev[v]]` with `prev = self.up[j - 1]`.

2. -1 Stays -1

A missing ancestor is `-1`, and in Python `prev[-1]` reads the last node instead of failing: check `prev[v] == -1` while building and stop at `node == -1` while answering.

3. Pay Once, Ask Often

Building costs O(N log N) time and space; each question jumps once per set bit of `k`, O(log N), instead of walking up to N parents.

Theory Context•Depth-First Search (DFS)

HardLC 1483

Kth Ancestor of a Tree Node (LeetCode 1483)

You will see how storing every node's 1st, 2nd, 4th, 8th, ... ancestor turns any k-steps-up question into one jump per set bit of k.

Target Frequency:GoogleAmazon

Going up from a node one edge at a time, the first node you reach is its 1st ancestor (its parent), the next one its 2nd ancestor, and so on. Write a class TreeAncestor:

TreeAncestor(n, parent) receives the tree once.
getKthAncestor(node, k) returns the k-th ancestor of node, or -1 when fewer than k nodes lie above node.

The same tree answers up to 5 * 10⁴ questions.

Worked Examples

Example 1

Input:

["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]

Output:[null, 1, 0, -1]

⚖️Formal Constraints & Bounds

1 <= k <= n <= 5 * 10⁴
parent.length == n
parent[0] == -1
0 <= parent[i] < n for every 0 < i < n, and the parents form one tree rooted at node 0.
0 <= node < n
At most 5 * 10⁴ calls are made to getKthAncestor.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Example 1, parent = [-1, 0, 0, 1, 1, 2, 2], so self.LOG = (7).bit_length() = 3. The constructor builds three levels:

Level	Meaning	Row (node 0 to 6)	How
`self.up[0]`	1st ancestor	`[-1, 0, 0, 1, 1, 2, 2]`	the parent list
`self.up[1]`	2nd ancestor	`[-1, -1, -1, 0, 0, 0, 0]`	`prev[prev[v]]`, with `-1` kept for nodes 0, 1, 2
`self.up[2]`	4th ancestor	`[-1, -1, -1, -1, -1, -1, -1]`	the tree is only 2 levels deep

Scroll horizontally to see all columns, or expand to full screen

Then each question jumps once per set bit of k:

Call	`k` in binary	Jumps	Returns
`getKthAncestor(3, 1)`	`1`	`self.up[0][3] = 1`	1
`getKthAncestor(5, 2)`	`10`	`self.up[1][5] = 0`	0
`getKthAncestor(6, 3)`	`11`	`self.up[0][6] = 2`, then `self.up[1][2] = -1`: stop	-1

Scroll horizontally to see all columns, or expand to full screen

Building self.up[1][0] is where the trap sits: prev[0] == -1, and without that check prev[prev[0]] would read prev[-1] = 2, so node 0 would get node 2 as its 2nd ancestor.

Trace Input

["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]

Expected[null, 1, 0, -1]

Example 1, parent = [-1, 0, 0, 1, 1, 2, 2], so self.LOG = (7).bit_length() = 3. The constructor builds three levels:

Level	Meaning	Row (node 0 to 6)	How
`self.up[0]`	1st ancestor	`[-1, 0, 0, 1, 1, 2, 2]`	the parent list
`self.up[1]`	2nd ancestor	`[-1, -1, -1, 0, 0, 0, 0]`	`prev[prev[v]]`, with `-1` kept for nodes 0, 1, 2
`self.up[2]`	4th ancestor	`[-1, -1, -1, -1, -1, -1, -1]`	the tree is only 2 levels deep

Scroll horizontally to see all columns, or expand to full screen

Then each question jumps once per set bit of k:

Call	`k` in binary	Jumps	Returns
`getKthAncestor(3, 1)`	`1`	`self.up[0][3] = 1`	1
`getKthAncestor(5, 2)`	`10`	`self.up[1][5] = 0`	0
`getKthAncestor(6, 3)`	`11`	`self.up[0][6] = 2`, then `self.up[1][2] = -1`: stop	-1

Scroll horizontally to see all columns, or expand to full screen

Building self.up[1][0] is where the trap sits: prev[0] == -1, and without that check prev[prev[0]] would read prev[-1] = 2, so node 0 would get node 2 as its 2nd ancestor.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Store longer jumps once instead of walking one parent at a time: `self.up[j][v]` is the node `2^j` steps above `v`. Any `k` is a sum of powers of two, so a question takes one jump per set bit of `k`.
2	`self.up[0]` is the parent list; level `j` is two jumps of level `j - 1`: `prev[prev[v]]`. In the query, `if k >> j & 1:` then `node = self.up[j][node]`. `self.LOG = max(1, n.bit_length())` levels cover every `k <= n`.
3	The shape: `__init__` sets `self.LOG`, `self.up = [parent[:]]`, then for `j` from 1 appends `[... for v in range(n)]` built from `prev = self.up[j - 1]`. `getKthAncestor` loops `j` over `range(self.LOG)` and returns `node` at the end.
4	The trap: `-1` must stay `-1`. Write `-1 if prev[v] == -1 else prev[prev[v]]`, and `return -1` as soon as `node == -1`: in Python `prev[-1]` is the last node's entry, not an error.

Target: Kth Ancestor of a Tree Node (LeetCode 1483). `k <= n`, so every `k` is written with the bits `0..LOG-1`.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏢 The Analogy: Express Stops on a Metro Line

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

self.LOG = max(1, n.bit_length())
self.up = [parent[:]]
for j in range(1, self.LOG):
    prev = self.up[j - 1]
    self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
 
for j in range(self.LOG):
    if k >> j & 1:
        node = self.up[j][node]
        if node == -1:
            return -1
return node

💡 Summary

Letting -1 index the table: write -1 if prev[v] == -1 else prev[prev[v]] and return as soon as node == -1. Python reads prev[-1] as the last node's entry, so on LeetCode's example tree getKthAncestor(1, 3) would return 2 instead of -1.
Too few levels: self.LOG = max(1, n.bit_length()), not int(math.log2(n)). k can be as large as n, and on a chain of 8 nodes k = 8 needs the level 2³. The level count comes from the largest k (with k up to 10^10, k.bit_length() levels).
Filling the table node by node: build self.up[j] from the whole of self.up[j - 1]. Filling one node's levels at a time reads rows of parents that are not built yet, because parent[i] < i is not promised.
Testing the wrong bit: Test bit j of k with k >> j & 1, not k & j: k & j tests the level number itself, so k = 2 skips the 2-level jump and takes the 4-level one at j = 2.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns many "k steps up" questions into a precomputed table of power-of-two jumps.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Check prev[v] == -1 before prev[prev[v]], and return as soon as node == -1: Python reads prev[-1] as the last node's entry, so on LeetCode's example tree getKthAncestor(1, 3) would return 2 instead of -1.
self.LOG = max(1, n.bit_length()), not int(math.log2(n)): k can be as large as n, and on a chain of 8 nodes k = 8 needs the level 2³. The level count comes from the largest k: with k up to 10^10, as in Maximize Value of Function in a Ball Passing Game (LC 2836), you need k.bit_length() levels.
Build self.up[j] from the whole of self.up[j - 1], level by level: filling one node's levels at a time reads rows of parents that are not built yet, since parent[i] < i is not promised.
Test bit j of k with k >> j & 1, not k & j: k & j tests the level number itself, so k = 2 skips the 2-level jump and takes the 4-level one at j = 2.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Binary Lifting. The tree is fixed and the questions are many, so I precompute longer jumps once. For every node I store its 1st, 2nd, 4th, 8th ancestor and so on, in a table up where up[j][v] is 2 to the j steps above v. Level 0 is the parent list, and each next level is two jumps of the level before, up[j-1] applied twice, because 2 to the j steps are two jumps of 2 to the j-minus-1 steps each. To answer a question I read k in binary and jump once for each set bit, since the jumps add up in any order. The trap is the root: a missing ancestor is minus one, and in Python indexing with minus one silently reads the last node, so I check for minus one while building and stop as soon as I reach it. Building is O(N log N) time and space, and each question is O(log N).

So: self.up[j][v] holds the node 2^j steps above v; answer with one jump per set bit of k; -1 stays -1.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N log N) to build, O(log N) per query

SPACE COMPLEXITY

O(N log N)

self.up holds self.LOG lists of n integers: O(N log N). A query keeps only node and j: O(1) extra.

Formal Recurrence Relation

$T = \underbrace{N \cdot \log N}_{\text{build}} + \underbrace{Q \cdot \log N}_{\text{queries}}$

Derivation Progression

Level 0

N

self.up = [parent[:]] copies the parent list.

Levels 1 to LOG - 1

$(\log N) \cdot N$

Each level is one pass over every node: -1 if prev[v] == -1 else prev[prev[v]], O(1) per node.

One query

$\log N$

The loop reads each of self.LOG bits of k once, with at most one table read per bit.

Total

$O((N + Q) \log N)$

Built once, then Q questions of O(log N) each, instead of up to N steps each.

Variable Definitions

$N$

Number of nodes, n

$Q$

Number of getKthAncestor calls

$log N$

self.LOG = n.bit_length(), the number of levels in self.up

Memory Architecture & Bounds

🟣 Call Stack

O(1): no recursion

🔵 Auxiliary Heap

O(N log N): self.up has self.LOG rows of n entries

🟢 Output Space

O(1) per query: one node number

Boundary Best / Worst Cases

Best Case

A query with k a power of two: one table read, but the loop still turns self.LOG times, O(log N)

Average Case

O(log N) per query after an O(N log N) build

Worst Case

A query with every bit of k set: self.LOG jumps, still O(log N)

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Jumps of Every Power of Two

`self.up[j][v]` is the node `2^j` steps above `v`: level 0 is `parent`, and level `j` is `prev[prev[v]]` with `prev = self.up[j - 1]`.

2. -1 Stays -1

A missing ancestor is `-1`, and in Python `prev[-1]` reads the last node instead of failing: check `prev[v] == -1` while building and stop at `node == -1` while answering.

3. Pay Once, Ask Often

Building costs O(N log N) time and space; each question jumps once per set bit of `k`, O(log N), instead of walking up to N parents.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: KTH ANCESTOR OF A TREE NODE (LEETCODE 1483)

T = O(N log N) to build, O(log N) per queryS = O(N log N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Enough levels for every k	`self.LOG = max(1, n.bit_length())`	`k <= n`, so every `k` is written with the bits `0..LOG-1`.
Level 0: one step up	`self.up = [parent[:]]`	The parent list is already every node's 1st ancestor, with `-1` for the root.
Each level from the one before	`for j in range(1, self.LOG): prev = self.up[j - 1]`	Level `j` needs the whole of level `j - 1`, so levels are built in order, each over every node.
Two half jumps make one jump; -1 stays -1 (the trap)	`self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])`	`2^(j-1)` steps then `2^(j-1)` more is `2^j`. Without the check, `prev[-1]` reads the last node's entry instead of failing.
One jump per set bit of k	`for j in range(self.LOG): if k >> j & 1: node = self.up[j][node]`	`k` is a sum of powers of two, and jumps add up in any order.
Stop past the root	`if node == -1: return -1`	Fewer than `k` ancestors: return before `self.up[j][-1]` wraps around.
Answer	`return node`	Every set bit has been jumped: `node` is exactly `k` steps above the start.

Level

Meaning

Row (node 0 to 6)

How

self.up[0]

1st ancestor

[-1, 0, 0, 1, 1, 2, 2]

the parent list

self.up[1]

2nd ancestor

[-1, -1, -1, 0, 0, 0, 0]

prev[prev[v]], with -1 kept for nodes 0, 1, 2

self.up[2]

4th ancestor

[-1, -1, -1, -1, -1, -1, -1]

the tree is only 2 levels deep

Call

k in binary

Jumps

Returns

getKthAncestor(3, 1)

1

self.up[0][3] = 1

getKthAncestor(5, 2)

10

self.up[1][5] = 0

getKthAncestor(6, 3)

11

self.up[0][6] = 2, then self.up[1][2] = -1: stop

-1

Level

Meaning

Row (node 0 to 6)

How

self.up[0]

1st ancestor

[-1, 0, 0, 1, 1, 2, 2]

the parent list

self.up[1]

2nd ancestor

[-1, -1, -1, 0, 0, 0, 0]

prev[prev[v]], with -1 kept for nodes 0, 1, 2

self.up[2]

4th ancestor

[-1, -1, -1, -1, -1, -1, -1]

the tree is only 2 levels deep

Call

k in binary

Jumps

Returns

getKthAncestor(3, 1)

1

self.up[0][3] = 1

getKthAncestor(5, 2)

10

self.up[1][5] = 0

getKthAncestor(6, 3)

11

self.up[0][6] = 2, then self.up[1][2] = -1: stop

-1

self.LOG = max(1, n.bit_length()) self.up = [parent[:]] for j in range(1, self.LOG): prev = self.up[j - 1] self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)]) for j in range(self.LOG): if k >> j & 1: node = self.up[j][node] if node == -1: return -1 return node

Level

Meaning

Row (node 0 to 6)

How

self.up[0]

1st ancestor

[-1, 0, 0, 1, 1, 2, 2]

the parent list

self.up[1]

2nd ancestor

[-1, -1, -1, 0, 0, 0, 0]

prev[prev[v]], with -1 kept for nodes 0, 1, 2

self.up[2]

4th ancestor

[-1, -1, -1, -1, -1, -1, -1]

the tree is only 2 levels deep

Call

k in binary

Jumps

Returns

getKthAncestor(3, 1)

1

self.up[0][3] = 1

getKthAncestor(5, 2)

10

self.up[1][5] = 0

getKthAncestor(6, 3)

11

self.up[0][6] = 2, then self.up[1][2] = -1: stop

-1

Level

Meaning

Row (node 0 to 6)

How

self.up[0]

1st ancestor

[-1, 0, 0, 1, 1, 2, 2]

the parent list

self.up[1]

2nd ancestor

[-1, -1, -1, 0, 0, 0, 0]

prev[prev[v]], with -1 kept for nodes 0, 1, 2

self.up[2]

4th ancestor

[-1, -1, -1, -1, -1, -1, -1]

the tree is only 2 levels deep

Call

k in binary

Jumps

Returns

getKthAncestor(3, 1)

1

self.up[0][3] = 1

getKthAncestor(5, 2)

10

self.up[1][5] = 0

getKthAncestor(6, 3)

11

self.up[0][6] = 2, then self.up[1][2] = -1: stop

-1

Canonical Invariant

Concrete Code

Engineering Rationale

Enough levels for every k

self.LOG = max(1, n.bit_length())

`k <= n`, so every `k` is written with the bits `0..LOG-1`.

Level 0: one step up

self.up = [parent[:]]

The parent list is already every node's 1st ancestor, with `-1` for the root.

Each level from the one before

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

Level `j` needs the whole of level `j - 1`, so levels are built in order, each over every node.

Two half jumps make one jump; -1 stays -1 (the trap)

self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])

`2^(j-1)` steps then `2^(j-1)` more is `2^j`. Without the check, `prev[-1]` reads the last node's entry instead of failing.

One jump per set bit of k

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

`k` is a sum of powers of two, and jumps add up in any order.

Stop past the root

if node == -1:
    return -1

Fewer than `k` ancestors: return before `self.up[j][-1]` wraps around.

Answer

return node

Every set bit has been jumped: `node` is exactly `k` steps above the start.