Builds on Bottom-Up DFS and Fast Power, which you haven’t finished yet.
Binary Lifting (Kth Ancestor / LCA)
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.
Binary Lifting
- Only one pair of nodes is asked about, once, as in Lowest Common Ancestor of a Binary Tree (LC 236): a table built to answer many questions never pays for itself. See Bottom-Up DFS
| 1 | class TreeAncestor: |
| 2 | """Kth Ancestor of a Tree Node: up[j][v] is v's 2^j-th ancestor, so any k is a few |
| 3 | jumps. |
| 4 | Time: O(N log N) to build, O(log N) per query | Space: O(N log N) |
| 5 | """ |
| 6 | Â |
| 7 | def __init__(self, n: int, parent: list[int]) -> None: |
| 8 | self.LOG = max(1, n.bit_length()) # k <= n, so bits 0..LOG-1 cover every k |
| 9 | self.up = [parent[:]] # up[0][v]: v's parent (-1 for the root) |
| 10 | for j in range(1, self.LOG): |
| 11 | prev = self.up[j - 1] |
| 12 | # Two jumps of 2^(j-1) make one jump of 2^j; past the root stays -1 |
| 13 | self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)]) |
| 14 | Â |
| 15 | def getKthAncestor(self, node: int, k: int) -> int: |
| 16 | for j in range(self.LOG): |
| 17 | if k >> j & 1: # Bit j of k is set: jump 2^j levels up |
| 18 | node = self.up[j][node] |
| 19 | if node == -1: |
| 20 | return -1 # Past the root: stop before up[j][-1] wraps around |
| 21 | return node |
self.up[j][v] is the node exactly 2^j steps above v, or -1 when fewer than 2^j nodes lie above it.Store, for every node, where 2^j steps up lands: self.up[0] is the parent list, and each next level is two jumps of the level before, prev[prev[v]]. Then any k is a sum of powers of two, so getKthAncestor jumps once for each set bit of k: node = self.up[j][node] whenever k >> j & 1. This is correct because the jumps add up: 2^j steps followed by 2^j more is exactly 2^(j+1), and the bits of k add up to k, in any order. self.LOG = max(1, n.bit_length()) levels are enough, because k <= n. The trap is the root. A node with fewer than 2^j nodes above it has -1 in level j, and -1 must stay -1: check prev[v] == -1 before reading prev[prev[v]], and return -1 as soon as node == -1. In Python, prev[-1] is not an error but the last node's entry, so an unguarded table quietly turns "no ancestor" into a real node.
See it run
Binary lifting: build up[j], then jump along the bits of k
levels built 1k 5 = 101 in binary
Each circle is a tree node. The rows under the tree are up[0], up[1], ...: entry v of up[j] is the ancestor 2^j steps above node v, or -1.
nowthe node the table or the query is working onhalfwaythe node reached after the first of the two jumpslandsthe node a finished jump lands on
The tree has 10 nodes, so LOG = 4 levels are enough for any k up to 10. up[0] is the parent list.
Gotcha 1 of 5
- The trap
Gotcha 1: Reading
prev[prev[v]]without checkingprev[v] == -1Mistakeself.up.append([prev[prev[v]] for v in range(n)])Fixself.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])What happens:
-1means that the node has no ancestor that far up. Python readsprev[-1]as the last entry of the list, not as an error. So an uncheckedprev[prev[v]]turns a missing ancestor into a real node. The table then holds wrong jumps.Example: Kth Ancestor of a Tree Node (LC 1483): n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(1, 3)Mistake: returns 2Fix: returns -1
Deep Dive
Why the bits of k are enough
self.up[j][v] is the node 2^j steps above v. Level 0 is the parent list. Level j is two jumps of level j - 1: up[j][v] = up[j - 1][up[j - 1][v]]. Two jumps of 2^(j-1) steps make one jump of 2^j steps, so the rule is always true.
Every number k is a sum of different powers of two, and its binary digits say which ones. For k = 5, the binary form is 101, so 5 = 4 + 1. Climbing 1 step and then 4 steps is the same as climbing 5 steps. The order of the jumps does not matter, because every jump goes up the same single chain of parents.
So getKthAncestor visits each level j from 0 up, and jumps only when bit j of k is set. The loop runs LOG times, where LOG = max(1, n.bit_length()). One query costs O(log N), and the walk-up-one-step loop would cost O(k).
Example: in Kth Ancestor of a Tree Node (LC 1483), take parent = [-1, 0, 0, 1, 1, 2, 3, 3, 6, 8] (10 nodes). Node 9 has the ancestors 8, 6, 3, 1, 0, in that order. getKthAncestor(9, 5) jumps 1 step to node 8, then 4 steps to node 0. The answer is 0.
One trace: fill the table, then answer a query
The board uses the tree from the previous section. The rows under the tree are up[0], up[1], up[2] and up[3]. LOG is 4, because n = 10 has bit_length 4.
The build steps follow node 9. up[1][9] is 6: one step reaches 8, a second step reaches 6. up[2][9] is 1: two steps reach 6, two more steps reach 1. up[3][9] is -1: four steps reach 1, but node 1 has only one ancestor, so four more steps pass the root. That step is marked as the trap, and the check prev[v] == -1 is the reason the answer stays -1.
The query is getKthAncestor(9, 5), and 5 is 101 in binary. Bit 0 is set, so the node becomes up[0][9] = 8. Bit 1 is 0, so there is no jump. Bit 2 is set, so the node becomes up[2][8] = 0. Bit 3 is 0. The answer is 0, which matches the five parent steps 9, 8, 6, 3, 1, 0.
The trap: -1 must stay -1
-1 means "no ancestor that far up". A negative index in Python does not raise an error. It reads the list from the end, so prev[-1] is the last entry of prev.
Suppose the table is built as prev[prev[v]] with no check. For the tree above, up[0][0] is -1. Then up[1][0] reads prev[-1], which is prev[9], which is 8. The root now claims that two steps up is node 8. The table holds wrong jumps, and no exception is raised.
The same table gives getKthAncestor(9, 7) = 8. Node 9 has only 5 ancestors, so the correct answer is -1. The guard has two parts. In the build, write -1 if prev[v] == -1 else prev[prev[v]]. In the query, return -1 as soon as node == -1.
The level count can also be wrong. int(math.log2(n)) gives 3 for n = 8, but k = 8 needs bit 3. Use n.bit_length(). When k is larger than n, as in Maximize Value of Function in a Ball Passing Game (LC 2836), use k.bit_length().
The cost, and the neighbouring card
The table has LOG rows and n entries in each row. Building it costs O(N log N) time and O(N log N) space. After that, each query costs O(log N). For n = 50000 and 50000 queries, that is about 16 steps for each query, and no query walks the whole chain.
The table pays off only when there are many queries. A single question about two nodes, as in Lowest Common Ancestor of a Binary Tree (LC 236), is answered by one walk with the Ask Children card, and the table is not worth building.
The same table also finds the lowest common ancestor of many pairs. First lift the deeper node up by the difference of the depths, with the bits of that difference. Then lift both nodes together, from the highest level down to level 0, and jump only when the two landing nodes differ. Minimum Edge Weight Equilibrium Queries in a Tree (LC 2846) uses this idea.
The build must go level by level. up[j] needs the whole of up[j - 1], and a parent can come later in the list than its child, because the input does not promise parent[i] < i.
60-Second Pitch
"One question about two nodes needs only a walk. Here there are many queries about one tree, so I build a table first. up[j][v] is the node 2^j steps above v, or -1. Level 0 is the parent list. Each next level is two jumps of the level before: up[j][v] = up[j - 1][up[j - 1][v]], with -1 staying -1. To answer getKthAncestor(node, k), I read the bits of k. For each set bit j, I jump to up[j][node], and I return -1 as soon as the node is -1. The jumps add up to k steps. The build costs O(N log N) time and space, and each query costs O(log N). The level count is n.bit_length(), because k is at most n."
Common Questions
- Why is the table correct? Why are two jumps of
2^(j-1)one jump of2^j? Every jump goes from a node to its parent chain, so steps simply add. The node
2^(j-1)steps abovevisup[j - 1][v]. Going2^(j-1)steps above that node isup[j - 1][up[j - 1][v]]. The total is2^jsteps abovev.- What are the time and space of the build and of one query?
The build is
O(N log N)time andO(N log N)space, because there areLOGrows ofnentries. One query isO(log N), one step for each bit ofk. A plain walk up costsO(k)per query, which is too slow for many largek.- How many levels do you need?
- How do you find the lowest common ancestor with this table?
Compute the depth of each node. Lift the deeper node by the difference of the depths, using the bits of the difference. If the two nodes are now equal, that node is the answer. Otherwise go from the highest level down to level 0, and jump both nodes together whenever their landing nodes differ. The parent of the final pair is the lowest common ancestor.
- When would you not build this table?
When there is one question, or only a few. A single walk, as in Lowest Common Ancestor of a Binary Tree (LC 236), costs
O(N)with no preparation. The table costsO(N log N)to build, so it pays off only when the number of queries is large.
SWE Reasoning
Spot it
- Many queries ask "where do I land after
ksteps" on one tree, or on a map where every item has exactly one next item. kor the number of queries is too large to walk one step at a time.- The wording says k-th ancestor, lowest common ancestor of two nodes, or a path between two nodes.
- The structure does not change between queries, so a table built once can be reused.
kcan be as large as1010, so a loop over the steps is not possible.
The invariant, step by step
up[0]is the parent list:up[0][v]is the node 1 step abovev, or -1 for the root.- For
j >= 1,up[j][v]is two jumps ofup[j - 1]. Two jumps of2^(j-1)steps are2^jsteps, so the invariant holds one level at a time. - If
prev[v]is -1, the node has no ancestor2^(j-1)steps up, so it has none2^jsteps up. The entry stays -1. - A query reads the bits of
k. For each set bitj, it movesnodetoup[j][node]. The jumps add up to exactlyksteps, in any order. - If
nodebecomes -1, the walk has passed the root, and the query returns -1 at once. Otherwisenodeis thek-th ancestor after the last bit.
Traps
prev[prev[v]]with no check for -1. Python readsprev[-1]as the last entry, so a missing ancestor becomes a real node.- Jumping again after
nodeis -1. The next jump readsup[j][-1], which is the last node's entry. Return -1 first. int(math.log2(n))levels. Forn = 8,k = 8needs bit 3, and the table has only levels 0 to 2. Usen.bit_length().k & jin place ofk >> j & 1. The first form mixeskwith the level number. The second reads bitj.- Filling one node's levels at a time. Level
jneeds another node's levelj - 1, and that row may not be built yet. Fill one whole level at a time.
Practice
Builds on Bottom-Up DFS and Fast Power, which you haven’t finished yet.
Binary Lifting (Kth Ancestor / LCA)
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.
Binary Lifting
- Only one pair of nodes is asked about, once, as in Lowest Common Ancestor of a Binary Tree (LC 236): a table built to answer many questions never pays for itself. See Bottom-Up DFS
| 1 | class TreeAncestor: |
| 2 | """Kth Ancestor of a Tree Node: up[j][v] is v's 2^j-th ancestor, so any k is a few |
| 3 | jumps. |
| 4 | Time: O(N log N) to build, O(log N) per query | Space: O(N log N) |
| 5 | """ |
| 6 | Â |
| 7 | def __init__(self, n: int, parent: list[int]) -> None: |
| 8 | self.LOG = max(1, n.bit_length()) # k <= n, so bits 0..LOG-1 cover every k |
| 9 | self.up = [parent[:]] # up[0][v]: v's parent (-1 for the root) |
| 10 | for j in range(1, self.LOG): |
| 11 | prev = self.up[j - 1] |
| 12 | # Two jumps of 2^(j-1) make one jump of 2^j; past the root stays -1 |
| 13 | self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)]) |
| 14 | Â |
| 15 | def getKthAncestor(self, node: int, k: int) -> int: |
| 16 | for j in range(self.LOG): |
| 17 | if k >> j & 1: # Bit j of k is set: jump 2^j levels up |
| 18 | node = self.up[j][node] |
| 19 | if node == -1: |
| 20 | return -1 # Past the root: stop before up[j][-1] wraps around |
| 21 | return node |
self.up[j][v] is the node exactly 2^j steps above v, or -1 when fewer than 2^j nodes lie above it.Store, for every node, where 2^j steps up lands: self.up[0] is the parent list, and each next level is two jumps of the level before, prev[prev[v]]. Then any k is a sum of powers of two, so getKthAncestor jumps once for each set bit of k: node = self.up[j][node] whenever k >> j & 1. This is correct because the jumps add up: 2^j steps followed by 2^j more is exactly 2^(j+1), and the bits of k add up to k, in any order. self.LOG = max(1, n.bit_length()) levels are enough, because k <= n. The trap is the root. A node with fewer than 2^j nodes above it has -1 in level j, and -1 must stay -1: check prev[v] == -1 before reading prev[prev[v]], and return -1 as soon as node == -1. In Python, prev[-1] is not an error but the last node's entry, so an unguarded table quietly turns "no ancestor" into a real node.
See it run
Binary lifting: build up[j], then jump along the bits of k
levels built 1k 5 = 101 in binary
Each circle is a tree node. The rows under the tree are up[0], up[1], ...: entry v of up[j] is the ancestor 2^j steps above node v, or -1.
nowthe node the table or the query is working onhalfwaythe node reached after the first of the two jumpslandsthe node a finished jump lands on
The tree has 10 nodes, so LOG = 4 levels are enough for any k up to 10. up[0] is the parent list.
Gotcha 1 of 5
- The trap
Gotcha 1: Reading
prev[prev[v]]without checkingprev[v] == -1Mistakeself.up.append([prev[prev[v]] for v in range(n)])Fixself.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])What happens:
-1means that the node has no ancestor that far up. Python readsprev[-1]as the last entry of the list, not as an error. So an uncheckedprev[prev[v]]turns a missing ancestor into a real node. The table then holds wrong jumps.Example: Kth Ancestor of a Tree Node (LC 1483): n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(1, 3)Mistake: returns 2Fix: returns -1
Deep Dive
Why the bits of k are enough
self.up[j][v] is the node 2^j steps above v. Level 0 is the parent list. Level j is two jumps of level j - 1: up[j][v] = up[j - 1][up[j - 1][v]]. Two jumps of 2^(j-1) steps make one jump of 2^j steps, so the rule is always true.
Every number k is a sum of different powers of two, and its binary digits say which ones. For k = 5, the binary form is 101, so 5 = 4 + 1. Climbing 1 step and then 4 steps is the same as climbing 5 steps. The order of the jumps does not matter, because every jump goes up the same single chain of parents.
So getKthAncestor visits each level j from 0 up, and jumps only when bit j of k is set. The loop runs LOG times, where LOG = max(1, n.bit_length()). One query costs O(log N), and the walk-up-one-step loop would cost O(k).
Example: in Kth Ancestor of a Tree Node (LC 1483), take parent = [-1, 0, 0, 1, 1, 2, 3, 3, 6, 8] (10 nodes). Node 9 has the ancestors 8, 6, 3, 1, 0, in that order. getKthAncestor(9, 5) jumps 1 step to node 8, then 4 steps to node 0. The answer is 0.
One trace: fill the table, then answer a query
The board uses the tree from the previous section. The rows under the tree are up[0], up[1], up[2] and up[3]. LOG is 4, because n = 10 has bit_length 4.
The build steps follow node 9. up[1][9] is 6: one step reaches 8, a second step reaches 6. up[2][9] is 1: two steps reach 6, two more steps reach 1. up[3][9] is -1: four steps reach 1, but node 1 has only one ancestor, so four more steps pass the root. That step is marked as the trap, and the check prev[v] == -1 is the reason the answer stays -1.
The query is getKthAncestor(9, 5), and 5 is 101 in binary. Bit 0 is set, so the node becomes up[0][9] = 8. Bit 1 is 0, so there is no jump. Bit 2 is set, so the node becomes up[2][8] = 0. Bit 3 is 0. The answer is 0, which matches the five parent steps 9, 8, 6, 3, 1, 0.
The trap: -1 must stay -1
-1 means "no ancestor that far up". A negative index in Python does not raise an error. It reads the list from the end, so prev[-1] is the last entry of prev.
Suppose the table is built as prev[prev[v]] with no check. For the tree above, up[0][0] is -1. Then up[1][0] reads prev[-1], which is prev[9], which is 8. The root now claims that two steps up is node 8. The table holds wrong jumps, and no exception is raised.
The same table gives getKthAncestor(9, 7) = 8. Node 9 has only 5 ancestors, so the correct answer is -1. The guard has two parts. In the build, write -1 if prev[v] == -1 else prev[prev[v]]. In the query, return -1 as soon as node == -1.
The level count can also be wrong. int(math.log2(n)) gives 3 for n = 8, but k = 8 needs bit 3. Use n.bit_length(). When k is larger than n, as in Maximize Value of Function in a Ball Passing Game (LC 2836), use k.bit_length().
The cost, and the neighbouring card
The table has LOG rows and n entries in each row. Building it costs O(N log N) time and O(N log N) space. After that, each query costs O(log N). For n = 50000 and 50000 queries, that is about 16 steps for each query, and no query walks the whole chain.
The table pays off only when there are many queries. A single question about two nodes, as in Lowest Common Ancestor of a Binary Tree (LC 236), is answered by one walk with the Ask Children card, and the table is not worth building.
The same table also finds the lowest common ancestor of many pairs. First lift the deeper node up by the difference of the depths, with the bits of that difference. Then lift both nodes together, from the highest level down to level 0, and jump only when the two landing nodes differ. Minimum Edge Weight Equilibrium Queries in a Tree (LC 2846) uses this idea.
The build must go level by level. up[j] needs the whole of up[j - 1], and a parent can come later in the list than its child, because the input does not promise parent[i] < i.
60-Second Pitch
"One question about two nodes needs only a walk. Here there are many queries about one tree, so I build a table first. up[j][v] is the node 2^j steps above v, or -1. Level 0 is the parent list. Each next level is two jumps of the level before: up[j][v] = up[j - 1][up[j - 1][v]], with -1 staying -1. To answer getKthAncestor(node, k), I read the bits of k. For each set bit j, I jump to up[j][node], and I return -1 as soon as the node is -1. The jumps add up to k steps. The build costs O(N log N) time and space, and each query costs O(log N). The level count is n.bit_length(), because k is at most n."
Common Questions
- Why is the table correct? Why are two jumps of
2^(j-1)one jump of2^j? Every jump goes from a node to its parent chain, so steps simply add. The node
2^(j-1)steps abovevisup[j - 1][v]. Going2^(j-1)steps above that node isup[j - 1][up[j - 1][v]]. The total is2^jsteps abovev.- What are the time and space of the build and of one query?
The build is
O(N log N)time andO(N log N)space, because there areLOGrows ofnentries. One query isO(log N), one step for each bit ofk. A plain walk up costsO(k)per query, which is too slow for many largek.- How many levels do you need?
- How do you find the lowest common ancestor with this table?
Compute the depth of each node. Lift the deeper node by the difference of the depths, using the bits of the difference. If the two nodes are now equal, that node is the answer. Otherwise go from the highest level down to level 0, and jump both nodes together whenever their landing nodes differ. The parent of the final pair is the lowest common ancestor.
- When would you not build this table?
When there is one question, or only a few. A single walk, as in Lowest Common Ancestor of a Binary Tree (LC 236), costs
O(N)with no preparation. The table costsO(N log N)to build, so it pays off only when the number of queries is large.
SWE Reasoning
Spot it
- Many queries ask "where do I land after
ksteps" on one tree, or on a map where every item has exactly one next item. kor the number of queries is too large to walk one step at a time.- The wording says k-th ancestor, lowest common ancestor of two nodes, or a path between two nodes.
- The structure does not change between queries, so a table built once can be reused.
kcan be as large as1010, so a loop over the steps is not possible.
The invariant, step by step
up[0]is the parent list:up[0][v]is the node 1 step abovev, or -1 for the root.- For
j >= 1,up[j][v]is two jumps ofup[j - 1]. Two jumps of2^(j-1)steps are2^jsteps, so the invariant holds one level at a time. - If
prev[v]is -1, the node has no ancestor2^(j-1)steps up, so it has none2^jsteps up. The entry stays -1. - A query reads the bits of
k. For each set bitj, it movesnodetoup[j][node]. The jumps add up to exactlyksteps, in any order. - If
nodebecomes -1, the walk has passed the root, and the query returns -1 at once. Otherwisenodeis thek-th ancestor after the last bit.
Traps
prev[prev[v]]with no check for -1. Python readsprev[-1]as the last entry, so a missing ancestor becomes a real node.- Jumping again after
nodeis -1. The next jump readsup[j][-1], which is the last node's entry. Return -1 first. int(math.log2(n))levels. Forn = 8,k = 8needs bit 3, and the table has only levels 0 to 2. Usen.bit_length().k & jin place ofk >> j & 1. The first form mixeskwith the level number. The second reads bitj.- Filling one node's levels at a time. Level
jneeds another node's levelj - 1, and that row may not be built yet. Fill one whole level at a time.