Kth Ancestor of a Tree Node (LeetCode 1483)
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 thek-th ancestor ofnode, or-1when fewer thanknodes lie abovenode.
The same tree answers up to 5 * 104 questions.
Worked Examples
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]][null, 1, 0, -1]⚖️Formal Constraints & Bounds
1 <= k <= n <= 5 * 104parent.length == nparent[0] == -10 <= parent[i] < nfor every0 < i < n, and the parents form one tree rooted at node0.0 <= node < nAt most
5 * 104calls are made togetKthAncestor.
Core Insight
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 |
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 |
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.
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]][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 |
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 |
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.
The Math, Step by Step
1. The table of jumps
Write for the -th ancestor of node , or when fewer than nodes lie above . The code stores the jumps whose lengths are powers of two:
So up[0][v] is the parent of , up[1][v] is its 2nd ancestor, up[2][v] its 4th ancestor, and so on.
2. Building one row from the row before
A jump of levels is two jumps of levels, because :
| Case | up[j][v] |
|---|---|
the first half-jump already leaves the tree, prev[v] == -1 | |
| otherwise | prev[prev[v]], the second half-jump from where the first one landed |
Here prev is row . So each row takes one pass over the nodes.
3. Why any takes one jump per 1 bit
Write in binary, with each bit equal to 0 or 1. Going up levels is the same as going up levels for every set bit , one jump after the other. For example, is 110 in binary, so it is a jump of 2 levels followed by a jump of 4 levels.
The order of the jumps does not matter, because the lengths only add up. The code goes from the lowest bit to the highest.
is at most . The code uses LOG = max(1, n.bit_length()) rows, where n.bit_length() is the number of bits of . So , and every bit of has a row. A query makes at most LOG jumps, which is .
4. Stopping at
Once a jump leaves the tree, node is . The code must return at once. In Python, up[j][-1] does not fail. A negative index counts from the end of the list, so it reads the entry of the last node.
On Example 1 this goes wrong for getKthAncestor(0, 3). Node 0 is the root, so the correct answer is . is 11 in binary. Bit 0 jumps to up[0][0], which is . Without the check, bit 1 then reads up[1][-1], which is up[1][6], which is 0. The code would return 0. With if node == -1: return -1, it returns .
The table itself uses the same guard. -1 if prev[v] == -1 else prev[prev[v]] never reads prev[-1].
5. Example 1 by hand
n = 7, parent = [-1, 0, 0, 1, 1, 2, 2]. Here n.bit_length() is 3, because 7 is 111 in binary, so LOG = 3.
| Row | Jump length | up[j] for nodes 0 to 6 |
|---|---|---|
| 0 | 1 | [-1, 0, 0, 1, 1, 2, 2] |
| 1 | 2 | [-1, -1, -1, 0, 0, 0, 0] |
| 2 | 4 | [-1, -1, -1, -1, -1, -1, -1] |
For example, up[1][5] is up[0][up[0][5]] = up[0][2] = 0. Row 2 is all , because the tree has only 3 levels.
The picture shows the tree of Example 1. Node 0 is the root, nodes 1 and 2 are its children, 3 and 4 hang under 1, and 5 and 6 hang under 2. Every node in the bottom row is 2 levels below the root, which is why its entry in row 1 of the table is 0.
The three questions:
| Query | in binary | Jumps | Answer |
|---|---|---|---|
getKthAncestor(3, 1) | 1 | bit 0: up[0][3] = 1 | 1 |
getKthAncestor(5, 2) | 10 | bit 1: up[1][5] = 0 | 0 |
getKthAncestor(6, 3) | 11 | bit 0: up[0][6] = 2, then bit 1: up[1][2] = |
The answers 1, 0 and -1 are the expected output. In the last query, node 6 has only two ancestors, 2 and 0, so the jump of 2 from node 2 leaves the tree.
6. From the math to the code
| Math | In TreeAncestor |
|---|---|
| enough rows for every bit of | self.LOG = max(1, n.bit_length()) |
| = parent | self.up = [parent[:]] |
[-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)] | |
| bit of | if k >> j & 1: |
| jump levels | node = self.up[j][node] |
| left the tree | if node == -1: followed by return -1 |
Building the table takes time and space. Each query takes time, as the docstring says.
| 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. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Walking up a tree one parent at a time costs k steps per question, and with 5 * 104 questions on a chain of 5 * 104 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.
🔑 Why It Works
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.
Reading
prev[prev[v]]without checkingprev[v] == -1Writing
int(math.log2(n))levels instead ofn.bit_length()Filling one node's levels at a time
Testing
k & jinstead ofk >> j & 1Jumping again after
nodebecomes-1
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"getKthAncestor(node, k)", "the same tree answers up to 5 * 104 questions" and "1 <= k <= n <= 5 * 104": 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
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
The card's trap:
-1must stay-1, both while building (prev[v] == -1) and while answering (node == -1).Copy the parent list for level 0 (
parent[:]):self.up = [parent]shares the caller's list, so any later change to it silently changes the table.Don't store every node's full list of ancestors: on a chain of 5 * 10^4 nodes that is about 1.25 * 10^9 entries, while the table holds
self.LOGrows ofn, 8 * 10^5 entries.
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 isO(log N).
Complexity & Mathematical Proof
O(N log N) to build, O(log N) per query
Building is O(N log N): self.LOG = max(1, n.bit_length()) levels, about log2 n + 1, of one O(1) pass per node each. A query is O(log N) however large k is, because it reads each of the self.LOG bits once. The stages below show where each term comes from.
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.
Derivation Progression
N
self.up = [parent[:]] copies the parent list.
Each level is one pass over every node: -1 if prev[v] == -1 else prev[prev[v]], O(1) per node.
The loop reads each of self.LOG bits of k once, with at most one table read per bit.
Built once, then Q questions of O(log N) each, instead of up to N steps each.
Variable Definitions
Number of nodes, n
Number of getKthAncestor calls
self.LOG = max(1, n.bit_length()), the number of levels in self.up
Memory Architecture & Bounds
O(1): no recursion
O(N log N): self.up has self.LOG rows of n entries
O(1) per query: one node number
Boundary Best / Worst Cases
A query with k a power of two: one table read, but the loop still turns self.LOG times, O(log N)
O(log N) per query after an O(N log N) build
A query with every bit of k set: self.LOG jumps, still O(log N)
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "getKthAncestor(node, k)", "the same tree answers up to 5 * 104 questions". A fixed tree, many questions, and k as long as the tree: Binary Lifting, a table of power-of-two jumps built once.
and up to questions. Walking k parents per question is up to steps on a chain; the table has 16 levels of entries, in all, and each question takes at most 16 jumps.
The table holds entries: here, but for nodes and 20 levels, where compact integer arrays (Python's array module or NumPy) matter more than the algorithm.
Kth Ancestor of a Tree Node (LeetCode 1483)
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 thek-th ancestor ofnode, or-1when fewer thanknodes lie abovenode.
The same tree answers up to 5 * 104 questions.
Worked Examples
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]][null, 1, 0, -1]⚖️Formal Constraints & Bounds
1 <= k <= n <= 5 * 104parent.length == nparent[0] == -10 <= parent[i] < nfor every0 < i < n, and the parents form one tree rooted at node0.0 <= node < nAt most
5 * 104calls are made togetKthAncestor.
Core Insight
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 |
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 |
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.
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]][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 |
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 |
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.
The Math, Step by Step
1. The table of jumps
Write for the -th ancestor of node , or when fewer than nodes lie above . The code stores the jumps whose lengths are powers of two:
So up[0][v] is the parent of , up[1][v] is its 2nd ancestor, up[2][v] its 4th ancestor, and so on.
2. Building one row from the row before
A jump of levels is two jumps of levels, because :
| Case | up[j][v] |
|---|---|
the first half-jump already leaves the tree, prev[v] == -1 | |
| otherwise | prev[prev[v]], the second half-jump from where the first one landed |
Here prev is row . So each row takes one pass over the nodes.
3. Why any takes one jump per 1 bit
Write in binary, with each bit equal to 0 or 1. Going up levels is the same as going up levels for every set bit , one jump after the other. For example, is 110 in binary, so it is a jump of 2 levels followed by a jump of 4 levels.
The order of the jumps does not matter, because the lengths only add up. The code goes from the lowest bit to the highest.
is at most . The code uses LOG = max(1, n.bit_length()) rows, where n.bit_length() is the number of bits of . So , and every bit of has a row. A query makes at most LOG jumps, which is .
4. Stopping at
Once a jump leaves the tree, node is . The code must return at once. In Python, up[j][-1] does not fail. A negative index counts from the end of the list, so it reads the entry of the last node.
On Example 1 this goes wrong for getKthAncestor(0, 3). Node 0 is the root, so the correct answer is . is 11 in binary. Bit 0 jumps to up[0][0], which is . Without the check, bit 1 then reads up[1][-1], which is up[1][6], which is 0. The code would return 0. With if node == -1: return -1, it returns .
The table itself uses the same guard. -1 if prev[v] == -1 else prev[prev[v]] never reads prev[-1].
5. Example 1 by hand
n = 7, parent = [-1, 0, 0, 1, 1, 2, 2]. Here n.bit_length() is 3, because 7 is 111 in binary, so LOG = 3.
| Row | Jump length | up[j] for nodes 0 to 6 |
|---|---|---|
| 0 | 1 | [-1, 0, 0, 1, 1, 2, 2] |
| 1 | 2 | [-1, -1, -1, 0, 0, 0, 0] |
| 2 | 4 | [-1, -1, -1, -1, -1, -1, -1] |
For example, up[1][5] is up[0][up[0][5]] = up[0][2] = 0. Row 2 is all , because the tree has only 3 levels.
The picture shows the tree of Example 1. Node 0 is the root, nodes 1 and 2 are its children, 3 and 4 hang under 1, and 5 and 6 hang under 2. Every node in the bottom row is 2 levels below the root, which is why its entry in row 1 of the table is 0.
The three questions:
| Query | in binary | Jumps | Answer |
|---|---|---|---|
getKthAncestor(3, 1) | 1 | bit 0: up[0][3] = 1 | 1 |
getKthAncestor(5, 2) | 10 | bit 1: up[1][5] = 0 | 0 |
getKthAncestor(6, 3) | 11 | bit 0: up[0][6] = 2, then bit 1: up[1][2] = |
The answers 1, 0 and -1 are the expected output. In the last query, node 6 has only two ancestors, 2 and 0, so the jump of 2 from node 2 leaves the tree.
6. From the math to the code
| Math | In TreeAncestor |
|---|---|
| enough rows for every bit of | self.LOG = max(1, n.bit_length()) |
| = parent | self.up = [parent[:]] |
[-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)] | |
| bit of | if k >> j & 1: |
| jump levels | node = self.up[j][node] |
| left the tree | if node == -1: followed by return -1 |
Building the table takes time and space. Each query takes time, as the docstring says.
| 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. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Walking up a tree one parent at a time costs k steps per question, and with 5 * 104 questions on a chain of 5 * 104 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.
🔑 Why It Works
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.
Reading
prev[prev[v]]without checkingprev[v] == -1Writing
int(math.log2(n))levels instead ofn.bit_length()Filling one node's levels at a time
Testing
k & jinstead ofk >> j & 1Jumping again after
nodebecomes-1
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"getKthAncestor(node, k)", "the same tree answers up to 5 * 104 questions" and "1 <= k <= n <= 5 * 104": 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
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
The card's trap:
-1must stay-1, both while building (prev[v] == -1) and while answering (node == -1).Copy the parent list for level 0 (
parent[:]):self.up = [parent]shares the caller's list, so any later change to it silently changes the table.Don't store every node's full list of ancestors: on a chain of 5 * 10^4 nodes that is about 1.25 * 10^9 entries, while the table holds
self.LOGrows ofn, 8 * 10^5 entries.
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 isO(log N).
Complexity & Mathematical Proof
O(N log N) to build, O(log N) per query
Building is O(N log N): self.LOG = max(1, n.bit_length()) levels, about log2 n + 1, of one O(1) pass per node each. A query is O(log N) however large k is, because it reads each of the self.LOG bits once. The stages below show where each term comes from.
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.
Derivation Progression
N
self.up = [parent[:]] copies the parent list.
Each level is one pass over every node: -1 if prev[v] == -1 else prev[prev[v]], O(1) per node.
The loop reads each of self.LOG bits of k once, with at most one table read per bit.
Built once, then Q questions of O(log N) each, instead of up to N steps each.
Variable Definitions
Number of nodes, n
Number of getKthAncestor calls
self.LOG = max(1, n.bit_length()), the number of levels in self.up
Memory Architecture & Bounds
O(1): no recursion
O(N log N): self.up has self.LOG rows of n entries
O(1) per query: one node number
Boundary Best / Worst Cases
A query with k a power of two: one table read, but the loop still turns self.LOG times, O(log N)
O(log N) per query after an O(N log N) build
A query with every bit of k set: self.LOG jumps, still O(log N)
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "getKthAncestor(node, k)", "the same tree answers up to 5 * 104 questions". A fixed tree, many questions, and k as long as the tree: Binary Lifting, a table of power-of-two jumps built once.
and up to questions. Walking k parents per question is up to steps on a chain; the table has 16 levels of entries, in all, and each question takes at most 16 jumps.
The table holds entries: here, but for nodes and 20 levels, where compact integer arrays (Python's array module or NumPy) matter more than the algorithm.