Binary TreesProblem 33 of 35
Kth Ancestor of node in a Binary tree
Problem Statement
Given a binary tree and a node, find the kth ancestor of the given node. The 1st ancestor is the parent, 2nd ancestor is grandparent, and so on.
Example:
1
/ \
2 3
/ \
4 5
For node 5:
- 1st ancestor = 2
- 2nd ancestor = 1
- 3rd ancestor = null (doesn't exist)
For node 4:
- 1st ancestor = 2
- 2nd ancestor = 1
Approach 1: Brute Force (Store Path from Root)
Intuition
Find the path from root to the target node. The kth ancestor is the node at position (path_length - 1 - k) in the path.
Algorithm
- Find path from root to target node
- If k >= path length, return null (ancestor doesn't exist)
- Return the node at index (path_length - 1 - k)
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private boolean findPath(TreeNode root, int target, List<TreeNode> path) {
if (root == null) return false;
path.add(root);
if (root.val == target) return true;
if (findPath(root.left, target, path) ||
findPath(root.right, target, path)) {
return true;
}
path.remove(path.size() - 1);
return false;
}
public TreeNode kthAncestorBruteForce(TreeNode root, int target, int k) {
List<TreeNode> path = new ArrayList<>();
if (!findPath(root, target, path)) {
return null; // Target not found
}
int n = path.size();
// kth ancestor is at index (n - 1 - k)
int ancestorIndex = n - 1 - k;
if (ancestorIndex < 0) {
return null; // k is too large
}
return path.get(ancestorIndex);
}
}Complexity Analysis
- Time Complexity: O(n) - Finding path takes O(n)
- Space Complexity: O(n) - Storing the path
Approach 2: Optimal (Recursive with Counter)
Intuition
Instead of storing the entire path, use recursion with a counter. When we find the target node, start counting ancestors as we backtrack. When count equals k, that's our answer.
Algorithm
- Recursively search for target node
- When found, return special signal and start counting
- As we backtrack, decrement counter
- When counter reaches 0, current node is the kth ancestor
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private TreeNode ancestor = null;
// Returns distance to target if found, -1 if not found, 0 if answer already found
private int findKthAncestor(TreeNode root, int target, int k) {
if (root == null) return -1;
// Found the target node
if (root.val == target) {
return 1; // Distance 1 means parent is 1st ancestor
}
int leftDist = findKthAncestor(root.left, target, k);
int rightDist = findKthAncestor(root.right, target, k);
// If answer already found or target not in subtree
if (leftDist == 0 || rightDist == 0) return 0;
if (leftDist == -1 && rightDist == -1) return -1;
int dist = (leftDist != -1) ? leftDist : rightDist;
// Current node is the kth ancestor
if (dist == k) {
ancestor = root;
return 0; // Signal that answer is found
}
return dist + 1;
}
public TreeNode kthAncestor(TreeNode root, int target, int k) {
ancestor = null;
findKthAncestor(root, target, k);
return ancestor;
}
}For Multiple Queries: Binary Lifting
Complexity Analysis
- Time Complexity: O(n + k) - O(n) to find target, O(k) to count back (bounded by O(n))
- Space Complexity: O(h) - Recursion stack depth for optimal, O(n) for path storage
Binary Lifting (for multiple queries):
- Preprocessing: O(n log n)
- Per query: O(log k)
Key Takeaways
- Path storage approach: Simple but uses O(n) space
- Recursive counting: Space-efficient, only O(h) stack space
- Binary Lifting: For multiple queries, preprocess in O(n log n), answer each in O(log n)
- Counting convention: 1st ancestor = parent, 2nd = grandparent, etc.
- Edge cases: k larger than depth of node, target not found