Understanding the Problem
We are given a binary tree and a target node. The goal is to find the kth ancestor of this node.
An ancestor of a node is any node in the path from the node to the root (excluding the node itself).
The 1st ancestor is the parent, the 2nd is the grandparent, and so on.
For example, in the following binary tree:
1
/ 2 3
/ 4 5
If the target node is 5
and k = 2
, we trace upward: 5 → 2 → 1. So the 2nd ancestor is 1
.
Step-by-Step Solution with Example
Step 1: Build a parent map
We first traverse the tree and store each node’s parent in a map. This helps us move upwards from any node without recursion.
Step 2: Start from the target node
Using the parent map, we begin at the target node and move to its parent. We repeat this process k
times.
Step 3: Count each jump
Each move upward reduces k
by 1. If at any point the parent is null
, it means we’ve reached the root or an ancestor doesn’t exist.
Step 4: Return the current node
If after k
jumps we’re at a valid node, that’s our answer. Otherwise, return null
.
Example Walkthrough
Tree:
1
/ 2 3
/ 4 5
Target node = 5
, k = 2
:
- Start at 5 → parent is 2 → k becomes 1
- Move to 2 → parent is 1 → k becomes 0
Since k = 0
and we’re at node 1
, the answer is 1
.
Edge Cases
Case 1: Target node has fewer than k ancestors
Tree:
1
/ 2 3
/
4
Target node =
4
,
k = 3
Path: 4 → 3 → 1 → null →
k = 0?
Since we ran out of ancestors before reaching
k
steps, the output is
null
.
Case 2: Target node is the root
Tree:
1
Target node =
1
,
k ≥ 1
The root has no parent, so any k
th ancestor is
null
.
Case 3: Deep ancestor in a skewed tree
Tree:
1
/
2
/
3
Target node =
3
,
k = 2
Path: 3 → 2 → 1 → Done → Answer is
1
.
Case 4: Empty tree
If the tree is empty (i.e., root is null
), we cannot find any ancestor. Output is always null
.
Finally
This problem teaches us how to think in terms of upward traversal in a tree using parent mapping.
It’s essential to handle edge cases like reaching the root too early or when the tree is empty.
A good solution avoids recursion for upward traversal and uses simple loops with a parent map, making it efficient and easy to follow.
Comments
Loading comments...