Leetcode Problem 1483. Kth Ancestor of a Tree Node

1483. Kth Ancestor of a Tree Node

Leetcode Solutions

Binary Lifting for Kth Ancestor Query

  1. Initialize a 2D array dp where dp[i][j] will store the 2^i-th ancestor of node j.\n2. Set dp[0][j] to be the parent of node j for all nodes j.\n3. For each power of two (i from 1 to log2(n)), compute dp[i][j] using dp[i-1][j] and dp[i-1][dp[i-1][j]].\n4. To answer a query getKthAncestor(node, k), convert k to binary.\n5. For each set bit in the binary representation of k, jump to the corresponding ancestor.\n6. If at any point the ancestor is -1, return -1 as the kth ancestor does not exist.
UML Thumbnail

Direct Ancestor Traversal

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...