Press "Enter" to skip to content

花花酱 LeetCode 1483. Kth Ancestor of a Tree Node

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

Implement the function getKthAncestor(int node, int k) to return the k-th ancestor of the given node. If there is no such ancestor, return -1.

The k-th ancestor of a tree node is the k-th node in the path from that node to the root.





Explanation: TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]); treeAncestor.getKthAncestor(3, 1); // returns 1 which is the parent of 3 treeAncestor.getKthAncestor(5, 2); // returns 0 which is the grandparent of 5 treeAncestor.getKthAncestor(6, 3); // returns -1 because there is no such ancestor


  • 1 <= k <= n <= 5*10^4
  • parent[0] == -1 indicating that 0 is the root node.
  • 0 <= parent[i] < n for all 0 < i < n
  • 0 <= node < n
  • There will be at most 5*10^4 queries.

Solution: LogN ancestors

  1. Build the tree from parent array
  2. Traverse the tree
  3. For each node stores up to logn ancestros, 2^0-th, 2^1-th, 2^2-th, …

When k comes in, each node take the highest bit h out, and query its 2^h’s ancestors with k <- (k – 2^h). There will be at most logk recursive query. When it ends? k == 0, we found the ancestors which is the current node. Or node == 0 and k > 0, we already at root which doesn’t have any ancestors so return -1.

Time complexity:
Construction: O(nlogn)
Query: O(logk)

Space complexity:


DP method


Solution 2: Binary Search

credit: Ziwu Zhou

Construction: O(n)

Traverse the tree in post order, for each node record its depth and id (visiting order).
For each depth, store all the nodes and their ids.

Query: O(logn)

Get the depth and id of the node, if k > d, return -1.
Use binary search to find the first node at depth[d – k] that has a id greater than the query’s one That node is the k-th ancestor of the node.


If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website


Be First to Comment

Leave a Reply