#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/walkthrough-3

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/binary-lifting/walkthrough-3

Repovive

Walkthrough - Binary Lifting | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Walkthrough

(Sample queries)

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)