Log inSign up
mediumgeeksforgeeksNot Started

Kth Ancestor of a Node in Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree of size N and two integers k and node, find the kth ancestor of the given node in the binary tree. If no such ancestor exists, return -1.

An ancestor of a node is any node on the path from the root to that node, excluding the node itself. The 1st ancestor is its direct parent.

Example 1 · Example 1: Standard Tree:

Input: root = [1, 2, 3, 4, 5], k = 2, node = 4 Tree: 1 / \ 2 3 / \ 4 5
Output: 1
Explanation: 1st ancestor of 4 is 2. 2nd ancestor of 4 is 1.

Example 2 · Example 2: Ancestor Out of Bounds:

Input: root = [1, 2, 3], k = 2, node = 2 Tree: 1 / \ 2 3
Output: -1
Explanation: 2 only has 1 ancestor (node 1). The 2nd ancestor does not exist.

Constraints:

  • 1 <= N <= 105
  • 1 <= k <= 100
  • 1 <= Node.data <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply recursion stack unwinding to count ancestor distance.
  • Handle pass-by-reference state locking in backtracking.
  • Understand the path vector alternative.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find kth ancestor in a binary tree.
  • Walking upward k steps from target.
  • Single-query tree search.

Algorithmic Decision Tree:

  • Pass k by reference.
  • If node == null return null; if node.val == target return node.
  • Recurse left and right. If target found below, decrement k.
  • If k == 0 -> answer = node.val; k = -1 (lock answer).

Connected Patterns:

Lowest Common Ancestor of a Binary TreeAll Nodes Distance K in Binary TreeBinary Tree Paths

1. Path Array Collection

Intuition

Use standard path-finding DFS to store path of node values from root to target. If path.size() <= k, return -1. Otherwise, return path[path.size() - 1 - k].

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper findPath(root, target, path).
  2. Step 2: If target found, path contains [root ... target].
  3. Step 3: If path.size() <= k, return -1.
  4. Step 4: Return path[path.size() - 1 - k].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool findPath(TreeNode* root, int target, vector<int>& path) {
10 if (!root) return false;
11 path.push_back(root->val);
12 if (root->val == target) return true;
13 if (findPath(root->left, target, path) || findPath(root->right, target, path)) return true;
14 path.pop_back();
15 return false;
16 }
17 int kthAncestor(TreeNode* root, int k, int node) {
18 vector<int> path;
19 if (!findPath(root, node, path)) return -1;
20 int idx = (int)path.size() - 1 - k;
21 return (idx >= 0) ? path[idx] : -1;
22 }
23};
24
25int main() {
26 // Sample driver execution
27 cout << "Execution completed successfully." << endl;
28 return 0;
29}
30

Time & Space Complexity

  • Time complexity: O(n) — DFS searches for target once in O(n).
  • Space complexity: O(h) — Path array holds up to h nodes.

2. Parent Hash Map Traversal

Intuition

Map parent references for all nodes in tree using BFS. Locate target node. Step up parent pointers k times. If parent becomes null before k steps, return -1.

When to apply: When using parent pointers.

Algorithm

  1. Step 1: Build parent map using BFS: parent[childVal] = parentVal.
  2. Step 2: Start at cur = node.
  3. Step 3: Loop k times: if cur not in parent map, return -1; cur = parent[cur].
  4. Step 4: Return cur.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int kthAncestor(TreeNode* root, int k, int node) {
10 unordered_map<int, int> parent;
11 queue<TreeNode*> q;
12 q.push(root);
13 while (!q.empty()) {
14 TreeNode* cur = q.front(); q.pop();
15 if (cur->left) { parent[cur->left->val] = cur->val; q.push(cur->left); }
16 if (cur->right) { parent[cur->right->val] = cur->val; q.push(cur->right); }
17 }
18 int cur = node;
19 for (int i = 0; i < k; ++i) {
20 if (!parent.count(cur)) return -1;
21 cur = parent[cur];
22 }
23 return cur;
24 }
25};
26
27int main() {
28 // Sample driver execution
29 cout << "Execution completed successfully." << endl;
30 return 0;
31}
32

Time & Space Complexity

  • Time complexity: O(n) — BFS maps parents in O(n); k steps take O(k).
  • Space complexity: O(n) — Parent map stores n entries.

3. Single-Pass DFS Postorder Countdown

Intuition

Search for target node. On the way back up the call stack, decrement k. When k == 0, current node is the kth ancestor. Store its value and lock k to prevent further updates.

When to apply: Optimal gold-standard solution for single query in O(h) space.

Algorithm

  1. Step 1: Variable ans = -1. Pass k by reference.
  2. Step 2: Helper dfs(root, node, k): if null return null.
  3. Step 3: If root.val == node return root.
  4. Step 4: left = dfs(root.left); right = dfs(root.right).
  5. Step 5: If left or right found: k--; if k == 0: ans = root.val; return null; else return left ? left : right.

Ancestor Countdown Trace for root = [1, 2, 3, 4], k = 2, node = 4

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: DFS locates target node 4 at leaf
Visual state
Values and pointers at this exact step
tree
Root
1
L
2 (k=1)
Target
4 (Target)

Node order shown; add connections to display explicit tree edges.

1st ancestor: 2
Check / comparison
At node 2: k = 1
Decision / next transition
Node 2 is 1st ancestor. Need 2nd ancestor. Keep unwinding.
Why this step matters

Step 1: DFS locates target node 4 at leaf. Return 4. Unwind to parent 2. Decrement k: k = 2 - 1 = 1.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int ans = -1;
9 TreeNode* dfs(TreeNode* root, int& k, int node) {
10 if (!root) return nullptr;
11 if (root->val == node) return root;
12 TreeNode* l = dfs(root->left, k, node);
13 TreeNode* r = dfs(root->right, k, node);
14 if (l || r) {
15 k--;
16 if (k == 0) {
17 ans = root->val;
18 return nullptr;
19 }
20 return l ? l : r;
21 }
22 return nullptr;
23 }
24public:
25 int kthAncestor(TreeNode* root, int k, int node) {
26 ans = -1;
27 dfs(root, k, node);
28 return ans;
29 }
30};
31
32int main() {
33 // Sample driver execution
34 cout << "Execution completed successfully." << endl;
35 return 0;
36}
37

Time & Space Complexity

  • Time complexity: O(n) — Single traversal stops exploring after target is found.
  • Space complexity: O(h) — Call stack bounded by tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Path Array CollectionO(n)O(h)Collect ancestor list into array and index backwards.Array memory.
2.Parent Hash MapO(n)O(n)Map parents via BFS and climb parent links k times.Hash map overhead.
3.Single-Pass DFS Postorder CountdownOptimalO(n)O(h)Decrement k on call stack return; lock answer at k == 0.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • k exceeds distance to root: returns -1.
  • Target is root: root has no ancestors, returns -1.
  • k = 1: returns direct parent.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that for single query, simple DFS is O(n) and optimal. If there are Q queries (like LeetCode 1483), Binary Lifting preprocessing in O(n log n) with O(log n) per query is required.
  2. Make sure you lock k after finding the answer so ancestors higher up don't overwrite it.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the DFS approach decrement k during the recursion return phase (unwind) rather than during the downward exploration phase?

Back to DSA Sheet