Nodes at Distance K
When a Tree Isn't Enough
Here's a problem that breaks every tree pattern you've learned so far.
Problem (LC 863): Given a binary tree, a target node, and an integer \(k\), return all nodes at distance \(k\) from the target.
Target = 5, \(k\) = 2. The answer is [7, 4, 1].
Nodes 7 and 4 are straightforward — they're in the subtree of 5, two levels down. But node 1? It's the sibling of 5. To reach it from 5, you go up to 3, then down to 1.
That "up" direction is the problem. In a standard binary tree, nodes don't know their parents. You can go down (left child, right child) but never up. Distance \(k\) requires movement in all directions — left, right, and parent.
The insight: a tree is a graph where you've forgotten half the edges. Add parent pointers, and suddenly the tree becomes an undirected graph. Then "find nodes at distance \(k\)" is just BFS.
Step 1: Build Parent Pointers
A simple DFS from the root. At each node, record "this node's parent is the node that called me."
Now every node can reach three neighbors: left, right, and parent.
Parent Map Trace
| DFS Visit | Node | Parent Recorded |
|---|---|---|
| 1 | 3 | nullptr |
| 2 | 5 | 3 |
| 3 | 6 | 5 |
| 4 | 2 | 5 |
| 5 | 7 | 2 |
| 6 | 4 | 2 |
| 7 | 1 | 3 |
| 8 | 0 | 1 |
| 9 | 8 | 1 |
Step 2: BFS from the Target
Now treat the tree as an undirected graph. From any node, you can move to left, right, or parent. Run BFS from the target node, tracking distance. When distance equals \(k\), collect all nodes at that level.
You need a visited set to avoid revisiting nodes (since the graph is now undirected, you could loop back).
Full BFS Trace
Target = 5, \(k\) = 2.
| BFS Level | Distance | Queue Contents | Nodes Processed | Neighbors Added |
|---|---|---|---|---|
| Start | 0 | [5] | — | — |
| Level 0 | 0 | [5] | 5 | 6, 2, 3 (parent) |
| Level 1 | 1 | [6, 2, 3] | 6 → no unvisited neighbors | — |
| 2 → neighbors 7, 4 | 7, 4 | |||
| 3 → neighbor 1 (right; left=5 visited) | 1 | |||
| Level 2 | 2 | [7, 4, 1] | distance = \(k\) → collect all | [7, 4, 1] |
At distance 2, we collect [7, 4, 1]. Done.
Notice how node 3 was reached at distance 1 (going UP from 5), and then node 1 was reached at distance 2 (going DOWN from 3). The BFS naturally handles the up-then-down path.
The Code
void buildParentMap(TreeNode* node, TreeNode* parent,
unordered_map<TreeNode*, TreeNode*>& parentMap) {
if (!node) return;
parentMap[node] = parent;
buildParentMap(node->left, node, parentMap);
buildParentMap(node->right, node, parentMap);
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
unordered_map<TreeNode*, TreeNode*> parentMap;
buildParentMap(root, nullptr, parentMap);
queue<TreeNode*> bfsQueue;
unordered_set<TreeNode*> visited;
bfsQueue.push(target);
visited.insert(target);
int currentDistance = 0;
while (!bfsQueue.empty()) {
if (currentDistance == k) {
vector<int> result;
while (!bfsQueue.empty()) {
result.push_back(bfsQueue.front()->val);
bfsQueue.pop();
}
return result;
}
int levelSize = bfsQueue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = bfsQueue.front();
bfsQueue.pop();
for (TreeNode* neighbor : {node->left, node->right, parentMap[node]}) {
if (neighbor && visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
bfsQueue.push(neighbor);
}
}
}
currentDistance++;
}
return {};
}
Complexity: \(O(n)\) time for building the parent map + \(O(n)\) for BFS = \(O(n)\) total. \(O(n)\) space for parent map and visited set.
Tree-as-Graph Thinking
This problem marks a turning point. Up until now, a tree was a top-down hierarchy — you started at the root and moved toward leaves. Parent pointers flip that assumption.
Once you add parent edges, the tree becomes a generic undirected graph. And graph problems have graph solutions: BFS for shortest distance, DFS for connected components, etc.
We're only scratching the surface here. The Graph course teaches BFS and DFS in their full generality. What this lesson teaches is the conversion: how to take a tree and make it behave like a graph when the problem demands it.
When a tree problem asks you to move in a direction that tree edges don't support, add the missing edges. Parent pointers are the most common addition, but the next lesson will show you adjacency lists.
Why Not Pure Tree Recursion?
You could solve this without parent pointers using a pure recursive approach — compute distance from the target in the subtree, and separately compute distance going through the target's ancestors. It works, but the logic splits into cases (target in left subtree vs right subtree, distance going up vs down) and is significantly harder to get right.
The parent-pointer + BFS approach is clean because it reduces the tree problem to a graph problem you already know how to solve. In an interview, clarity beats cleverness.
Try It
The starter code has a distanceK function with a TODO. Fill in the body.
Predict before running: What happens when \(k = 0\)? The BFS starts at the target, immediately reaches distance 0, and returns [target->val]. Just the target itself.
Challenge: What if the target is the root and \(k\) exceeds the tree height? BFS will exhaust all nodes before reaching distance \(k\) and return an empty list. Make sure your code handles this gracefully.
Edge Cases to Watch For
- Target is the root (null parent pointer): The parent pointer for root is
nullptr. Your BFS neighbor loop must checkif (neighbor && ...)to avoid pushing null into the queue and crashing. - Parent map keyed by value instead of pointer: The parent map must use
TreeNode*pointers as keys, notintvalues. If you accidentally key by value, duplicate node values would overwrite each other and corrupt the map.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| LC 863 — All Nodes Distance K in Binary Tree | leetcode.com/problems/all-nodes-distance-k-in-binary-tree | Medium |
| LC 2385 — Amount of Time for Binary Tree to Be Infected | leetcode.com/problems/amount-of-time-for-binary-tree-to-be-infected | Medium |