Log inSign up
mediumleetcodeNot Started

All Nodes Distance K in Binary Tree

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

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node in any order.

A tree edge allows traversal in both directions (child to parent as well as parent to child).

Example 1 · Example 1: Target node 5 with K = 2:

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2 Tree: 3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4
Output: [7, 4, 1]
Explanation: Nodes at distance 2 from target node 5 are: 7 (via 2), 4 (via 2), and 1 (via 3).

Example 2 · Example 2: Target is Root with K = 1:

Input: root = [1], target = 1, k = 3 Tree: 1
Output: []
Explanation: No nodes exist at distance 3 from node 1.

Constraints:

  • The number of nodes in the tree is in the range [1, 500].
  • 0 <= Node.val <= 500
  • All the values Node.val are unique.
  • target is the value of one of the nodes in the tree.
  • 0 <= k <= 1000

What You'll Learn

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

  • Learn how to augment a tree with parent pointers for bidirectional navigation.
  • Master radial BFS from an arbitrary starting node.
  • Prevent infinite cycles in undirected tree graphs using a visited set.

Pattern Recognition Trigger

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

Signals to Look For:

  • Distance k from an arbitrary internal target node.
  • Need to traverse both downwards and upwards in a tree.
  • Shortest path in unweighted graph/tree.

Algorithmic Decision Tree:

  • If k == 0 -> return [target.val].
  • Step 1: Traverse tree to build parent map parentMap[child] = parent.
  • Step 2: Queue BFS starting at target, visited.add(target).
  • Step 3: Expand 3 neighbors: left, right, parent until distance == k.

Connected Patterns:

Burning TreeAmount of Time for Binary Tree to Be InfectedShortest Path in Undirected Graph

1. Convert to Undirected Graph + BFS

Intuition

Traverse the tree to construct an undirected adjacency list map where every edge between parent and child is bidirectional. Then run standard BFS from target up to radius k.

When to apply: When treating the problem strictly as a graph problem.

Algorithm

  1. Step 1: Traverse the tree using DFS to build graph adjacency list: graph[u].push(v) and graph[v].push(u).
  2. Step 2: Initialize a queue with target and visited set with target.
  3. Step 3: Run BFS level by level. Increment distance after each level.
  4. Step 4: When distance == k, return all elements currently in queue.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void buildGraph(TreeNode* node, TreeNode* parent, unordered_map<int, vector<int>>& adj) {
10 if (!node) return;
11 if (parent) {
12 adj[node->val].push_back(parent->val);
13 adj[parent->val].push_back(node->val);
14 }
15 buildGraph(node->left, node, adj);
16 buildGraph(node->right, node, adj);
17 }
18 vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
19 unordered_map<int, vector<int>> adj;
20 buildGraph(root, nullptr, adj);
21 queue<int> q;
22 unordered_set<int> visited;
23 q.push(target->val);
24 visited.insert(target->val);
25 int dist = 0;
26 while (!q.empty()) {
27 if (dist == k) {
28 vector<int> ans;
29 while (!q.empty()) { ans.push_back(q.front()); q.pop(); }
30 return ans;
31 }
32 int sz = q.size();
33 for (int i = 0; i < sz; ++i) {
34 int curr = q.front(); q.pop();
35 for (int nxt : adj[curr]) {
36 if (!visited.count(nxt)) {
37 visited.insert(nxt);
38 q.push(nxt);
39 }
40 }
41 }
42 dist++;
43 }
44 return {};
45 }
46};
47
48int main() {
49 // Sample driver execution
50 cout << "Execution completed successfully." << endl;
51 return 0;
52}
53

Time & Space Complexity

  • Time complexity: O(n) — Building graph takes O(n) and BFS visits at most n nodes.
  • Space complexity: O(n) — Adjacency list stores 2*(n-1) edges, taking O(n) memory.

2. Parent Pointer Map + Radial DFS

Intuition

Store parent pointers for each node using a hash map. Then run a recursive DFS starting from target node, moving to left, right, and parent while decrementing k. Maintain a visited set to avoid backtracking.

When to apply: When recursion is preferred over queue-based BFS.

Algorithm

  1. Step 1: Traverse the tree and store parent pointers in parentMap: parentMap.set(node, parent).
  2. Step 2: Call dfs(target, null, k, result).
  3. Step 3: If k == 0, add node.val to result and return.
  4. Step 4: Recurse on left child, right child, and parent, passing k - 1 and avoiding previous node.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void mapParents(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, TreeNode*>& parentMap) {
10 if (!node) return;
11 parentMap[node] = parent;
12 mapParents(node->left, node, parentMap);
13 mapParents(node->right, node, parentMap);
14 }
15 void dfs(TreeNode* node, TreeNode* from, int k, unordered_map<TreeNode*, TreeNode*>& parentMap, vector<int>& res) {
16 if (!node) return;
17 if (k == 0) {
18 res.push_back(node->val);
19 return;
20 }
21 if (node->left != from) dfs(node->left, node, k - 1, parentMap, res);
22 if (node->right != from) dfs(node->right, node, k - 1, parentMap, res);
23 TreeNode* p = parentMap[node];
24 if (p && p != from) dfs(p, node, k - 1, parentMap, res);
25 }
26 vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
27 unordered_map<TreeNode*, TreeNode*> parentMap;
28 mapParents(root, nullptr, parentMap);
29 vector<int> res;
30 dfs(target, nullptr, k, parentMap, res);
31 return res;
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n) — Parent map traversal visits all n nodes; DFS visits at most n nodes.
  • Space complexity: O(n) — Hash map stores n parent references; recursion call stack up to O(n).

3. Parent Pointer Map + Radial BFS

Intuition

Build a parent map using BFS/DFS. Then execute a level-by-level BFS starting from target. Use a visited set to avoid re-visiting nodes. As soon as current level equals k, the queue contains precisely the answer nodes.

When to apply: Optimal gold-standard solution for finding all nodes at distance k.

Algorithm

  1. Step 1: Traverse the tree with BFS/DFS to build parent map parentMap[child] = parent.
  2. Step 2: Enqueue target into BFS queue; mark target as visited.
  3. Step 3: Run BFS for k levels. For each node, explore left, right, and parent.
  4. Step 4: After k iterations, all nodes in the queue are at distance k. Return their values.

Radial BFS Trace for Target = 5, K = 2

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Map parent pointers: parent[5]=3, parent[1]=3
Visual state
Values and pointers at this exact step
tree
Root (Parent)
3
L (Target)
5
R (Sibling)
1

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

target: 5
Check / comparison
Queue: [5], Visited: {5}, Current Distance: 0
Decision / next transition
Expand neighbors of 5: left=null, right=null, parent=3.
Why this step matters

Step 1: Map parent pointers: parent[5]=3, parent[1]=3. Target is node 5. Start BFS queue with [5] at distance 0.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
10 unordered_map<TreeNode*, TreeNode*> parentMap;
11 queue<TreeNode*> q;
12 q.push(root);
13 while (!q.empty()) {
14 TreeNode* curr = q.front(); q.pop();
15 if (curr->left) { parentMap[curr->left] = curr; q.push(curr->left); }
16 if (curr->right) { parentMap[curr->right] = curr; q.push(curr->right); }
17 }
18 unordered_set<TreeNode*> visited;
19 q.push(target);
20 visited.insert(target);
21 int dist = 0;
22 while (!q.empty()) {
23 if (dist == k) break;
24 int sz = q.size();
25 for (int i = 0; i < sz; ++i) {
26 TreeNode* curr = q.front(); q.pop();
27 if (curr->left && !visited.count(curr->left)) {
28 visited.insert(curr->left);
29 q.push(curr->left);
30 }
31 if (curr->right && !visited.count(curr->right)) {
32 visited.insert(curr->right);
33 q.push(curr->right);
34 }
35 if (parentMap.count(curr) && !visited.count(parentMap[curr])) {
36 visited.insert(parentMap[curr]);
37 q.push(parentMap[curr]);
38 }
39 }
40 dist++;
41 }
42 vector<int> res;
43 while (!q.empty()) {
44 res.push_back(q.front()->val);
45 q.pop();
46 }
47 return res;
48 }
49};
50
51int main() {
52 // Sample driver execution
53 cout << "Execution completed successfully." << endl;
54 return 0;
55}
56

Time & Space Complexity

  • Time complexity: O(n) — Parent map takes O(n) and BFS stops at distance k (visiting at most n nodes).
  • Space complexity: O(n) — Parent hash map, queue, and visited set all take O(n) space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Graph Conversion + BFSO(n)O(n)Build full adjacency list graph for all nodes, then run BFS.Graph building overhead.
2.Parent Map + Radial DFSO(n)O(n)Map parents and recurse outward in 3 directions.Deep recursion.
3.Parent Map + Radial BFSOptimalO(n)O(n)BFS level-by-level outward from target; stops early when level == k.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • k = 0: Output is just [target.val].
  • target is root: No parent traversal needed, only downward search.
  • k exceeds max depth: Empty array [] returned.
  • Single node tree: If k=0 returns [root.val], if k>0 returns [].

Interview Tips & Best Practices

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

  1. Clarify whether node values are unique (LeetCode guarantees unique values).
  2. Mention that converting to an explicit adjacency list is also valid, but parent map uses less memory.
  3. Point out that BFS early exits at distance k without visiting the rest of the tree.

Quick Comprehension Check

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

1.Why can't we simply run a standard downward tree DFS/BFS from the target node to find all distance k nodes?

Back to DSA Sheet