How hard is LeetCode 1483. Kth Ancestor of a Tree Node?

LeetCode 1483. Kth Ancestor of a Tree Node is rated Hard on LeetCode.

Kth Ancestor of a Tree Node — LeetCode 1483 Python Solution

HardBit ManipulationTreeDepth-First SearchBreadth-First SearchDesignBinary SearchDynamic Programming

Problem: #1483
Pattern: Bit Manipulation
Reading time: 4 min
Source: leetcode.com

The problem

You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of ith node. The root of the tree is node 0.

Example

Input: ["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
Output: [null, 1, 0, -1]
Explanation: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

Python solution

Python

class TreeAncestor:
    def __init__(self, n: int, parent: List[int]):
        self.p = [[-1] * 18 for _ in range(n)]
        for i, fa in enumerate(parent):
            self.p[i][0] = fa
        for j in range(1, 18):
            for i in range(n):
                if self.p[i][j - 1] == -1:
                    continue
                self.p[i][j] = self.p[self.p[i][j - 1]][j - 1]

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(17, -1, -1):
            if k >> i & 1:
                node = self.p[node][i]
                if node == -1:
                    break
        return node


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(n \times \log n), where n is the number of nodes in the tree auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1483. Kth Ancestor of a Tree Node is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1483. Kth Ancestor of a Tree Node?: LeetCode 1483. Kth Ancestor of a Tree Node is rated Hard on LeetCode.
What topics does LeetCode 1483. Kth Ancestor of a Tree Node cover?: LeetCode 1483. Kth Ancestor of a Tree Node is tagged Bit Manipulation, Tree, Depth-First Search, Breadth-First Search, Design, Binary Search and Dynamic Programming on LeetCode.