Find the K-th Ancestor of a Chosen Node
Solve this ProblemYou are given the root of a binary tree with distinct node values, a value target and an integer k. The 1st ancestor of a node is its parent, the 2nd ancestor is its parent's parent, and so on up towards the root. Return the value of the k-th ancestor of the node that holds target. If the target is not in the tree, or the node has fewer than k ancestors, return -1.
You can record the path from the root and count back from its end, or let the recursion count the steps upward as it returns from the target.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes ≤ 100, and every node value is distinct, 1 ≤ node.val ≤ 1000 - ◆
target is a value between 1 and 1000 that may or may not be in the tree; 1 ≤ k ≤ 100 - ◆
The tree is given as its root node; each node has a val, a left child and a right child - ◆
The 1st ancestor of a node is its parent, the 2nd is the parent of its parent, and so on. Return the value of the k-th ancestor of the node holding target, or -1 if the target is not in the tree or the node has fewer than k ancestors
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Record the Root-to-Node Path, Then Index Back From the End
GoodThe ancestors of a node are exactly the nodes before it on its path from the root. Find that path with a depth-first search that appends a node on entering and removes it when the target is not below it. If the target was never found, answer -1. The path lists the target last, its parent second to last, and so on, so the k-th ancestor sits k positions before the end: index (length − 1 − k). If that index is negative the node has fewer than k ancestors, so the answer is -1. O(n) time, and the path uses O(h) space.
O(n)O(h)1class Solution {
2 public int kthAncestor(TreeNode root, int target, int k) {
3 List<Integer> path = new ArrayList<>();
4 if (!pathTo(root, target, path)) return -1;
5 int index = path.size() - 1 - k;
6 return index >= 0 ? path.get(index) : -1;
7 }
8
9 private boolean pathTo(TreeNode node, int target, List<Integer> path) {
10 if (node == null) return false;
11 path.add(node.val);
12 if (node.val == target) return true;
13 if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) return true;
14 path.remove(path.size() - 1);
15 return false;
16 }
17}Optimal — Count Steps Upward While the Recursion Unwinds
OptimalLet a helper return "how many steps is this node above the target", or -1 if the target is not in its subtree. The target itself returns 0. Any other node asks its left child and then its right child; if neither contains the target it returns -1; otherwise its own distance is the child's answer plus 1. The moment that distance equals k, this node is the k-th ancestor: store its value. Nothing else is needed — no path is stored, only a single answer variable. The search stops looking once the target is found in a subtree, and uses O(h) recursion space.
O(n)O(h)1class Solution {
2 private int found;
3
4 public int kthAncestor(TreeNode root, int target, int k) {
5 found = -1;
6 up(root, target, k);
7 return found;
8 }
9
10 private int up(TreeNode node, int target, int k) {
11 if (node == null) return -1;
12 if (node.val == target) return 0;
13 int d = up(node.left, target, k);
14 if (d == -1) d = up(node.right, target, k);
15 if (d == -1) return -1;
16 d++;
17 if (d == k) found = node.val;
18 return d;
19 }
20}