Hard

Kth Ancestor of a Tree Node

LAB

Given a parent array and queries [node,k], return each node k ancestors upward, or -1.

EXAMPLES

Example 1

Input
{
  "parent": [
    -1,
    0,
    0,
    1,
    1,
    2,
    2
  ],
  "queries": [
    [
      3,
      1
    ],
    [
      5,
      2
    ],
    [
      6,
      3
    ]
  ]
}

Output
[
  1,
  0,
  -1
]

FUNCTION SHAPE

parent: intArrayqueries: intMatrix→intArray

SOLUTION NOTE

Binary lifting. up[i][j] = 2^j-th ancestor of i. Query by decomposing k into binary.

Reveal reference solution +

pythonREFERENCE

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.LOG = 20
        self.up = [[-1] * self.LOG for _ in range(n)]

        for i in range(n):
            self.up[i][0] = parent[i]

        for j in range(1, self.LOG):
            for i in range(n):
                if self.up[i][j-1] != -1:
                    self.up[i][j] = self.up[self.up[i][j-1]][j-1]

    def getKthAncestor(self, node: int, k: int) -> int:
        for j in range(self.LOG):
            if k & (1 << j):
                node = self.up[node][j]
                if node == -1:
                    return -1
        return node

TimeO(n log n) build, O(log k) query

SpaceO(n log n)

Open on LeetCode ↗