Leetcode Problem 1483. Kth Ancestor of a Tree Node

1483. Kth Ancestor of a Tree Node

Leetcode Solutions

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.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen