Walkthrough

Tree Structure:

 0 (root)
 / \
 1 2
 / \
 3 4

$parent = [-1, 0, 0, 1, 1]$ means: node $0$ has no parent (root), nodes $1$ and $2$ have parent $0$, nodes $3$ and $4$ have parent $1$.

Query $1$: $getKthAncestor(3, 1)$. Find the $1$st ancestor of node $3$

• $k = 1 = 01_2$ (binary), bit $0$ is set
• Jump $2^0 = 1$ step: node = up[3][0] = 1
• Result: $1$ (parent of $3$)

Query $2$: $getKthAncestor(3, 2)$. Find the $2$nd ancestor of node $3$

• $k = 2 = 10_2$ (binary), bit $1$ is set
• Jump $2^1 = 2$ steps: node = up[3][1] = 0
• Result: $0$ (grandparent of $3$)

Query $3$: $getKthAncestor(3, 3)$. Find the $3$rd ancestor of node $3$

• $k = 3 = 11_2$ (binary), bits $0$ and $1$ are set
• Jump $2^0 = 1$ step: node = up[3][0] = 1
• Jump $2^1 = 2$ steps: node = up[1][1] = -1 (no such ancestor)
• Result: $-1$ (node $3$ doesn't have a $3$rd ancestor)