All Nodes Distance K in Binary Tree — Problem & Solution
All Nodes Distance K in Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
All Nodes Distance K in Binary Tree is a medium coding problem on hash table, depth-first search and breadth-first search, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Hash Table, Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree whose node values are all distinct, the value target of one of its nodes, and an integer k.
Return the values of all nodes that are exactly k edges away from the target node — moving along tree edges in either direction, up to a parent or down to a child — sorted in ascending order.
Example 1
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [1,4,7]
Explanation: Two edges from 5: down to 7 and 4 (through 2), and up through 3 to 1. Sorted, that is 1, 4, 7.
Example 2
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 7, k = 1
Output: [2]
Explanation: 7 is a leaf; its only neighbour is its parent 2.
Example 3
Input: root = [1], target = 1, k = 3
Output: []
Explanation: No node is three edges away in a one-node tree.
Constraints
The number of nodes in the tree is in the range [1, 500]0 <= Node.val <= 500All the values Node.val are uniquetarget is the value of one of the nodes in the tree0 <= k <= 1000
Hints for All Nodes Distance K in Binary Tree
Hint 1
Going down from the target is easy; the trouble is going up, because a node does not know its parent.
Hint 2
Record every node's parent in one traversal (or turn the tree into an undirected graph). Then the tree is just a graph.
Hint 3
Run a breadth-first search from the target over children and parent links, never revisiting a node, and collect what sits at distance
k.
How to solve All Nodes Distance K in Binary Tree
Distances in a tree run through parents as well as children. Once each node's neighbours — its two children and its parent — are known, the nodes at distance k are exactly BFS layer k from the target.
Approach
- Traverse the tree once and record, for every node, its neighbours: the parent link in both directions. Since values are distinct (and at most 500), an adjacency list indexed by value works.
- Run BFS from
targetwith adistarray (−1 = unseen); stop expanding a node once it is at distancek. - Collect every value whose distance is exactly
k, in ascending order of value.
Why it works
Every tree edge appears in both directions in the adjacency lists, so the graph's shortest paths are the tree's paths; BFS assigns each node its true edge distance from the target, and the nodes with distance k are the answer.
Complexity
- Time —
O(n) — plus O(V) to scan values in order, V = 501 here - Space —
O(n)
Pitfalls
- Mark nodes as visited, or the walk bounces between a child and its parent forever.
k = 0answers just the target itself; a largekcan answer an empty list.- Return the values sorted ascending, as the statement fixes.
Reference solution
Python
from typing import List, Optional
def distanceK(root: Optional[TreeNode], target: int, k: int) -> List[int]:
adj = {}
stack = [root]
adj[root.val] = []
while stack:
node = stack.pop()
for child in (node.left, node.right):
if child is not None:
adj[child.val] = [node.val]
adj[node.val].append(child.val)
stack.append(child)
dist = {target: 0}
queue = [target]
head = 0
while head < len(queue):
u = queue[head]
head += 1
if dist[u] == k:
continue
for v in adj[u]:
if v not in dist:
dist[v] = dist[u] + 1
queue.append(v)
return sorted(v for v, d in dist.items() if d == k)Java
public static int[] distanceK(TreeNode root, int target, int k) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= 500; i++) adj.add(new ArrayList<>());
link(root, adj);
int[] dist = new int[501];
Arrays.fill(dist, -1);
dist[target] = 0;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.add(target);
while (!queue.isEmpty()) {
int u = queue.poll();
if (dist[u] == k) continue;
for (int v : adj.get(u)) {
if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.add(v); }
}
}
List<Integer> out = new ArrayList<>();
for (int v = 0; v <= 500; v++) if (dist[v] == k) out.add(v);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}
static void link(TreeNode node, List<List<Integer>> adj) {
for (TreeNode child : new TreeNode[] { node.left, node.right }) {
if (child == null) continue;
adj.get(node.val).add(child.val);
adj.get(child.val).add(node.val);
link(child, adj);
}
}C++
void linkTree(TreeNode* node, vector<vector<int>>& adj);
vector<int> distanceK(TreeNode* root, int target, int k) {
vector<vector<int>> adj(501);
linkTree(root, adj);
vector<int> dist(501, -1);
dist[target] = 0;
vector<int> queue = {target};
for (size_t h = 0; h < queue.size(); h++) {
int u = queue[h];
if (dist[u] == k) continue;
for (int v : adj[u]) {
if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.push_back(v); }
}
}
vector<int> out;
for (int v = 0; v <= 500; v++) if (dist[v] == k) out.push_back(v);
return out;
}
void linkTree(TreeNode* node, vector<vector<int>>& adj) {
for (TreeNode* child : {node->left, node->right}) {
if (!child) continue;
adj[node->val].push_back(child->val);
adj[child->val].push_back(node->val);
linkTree(child, adj);
}
}JavaScript
var distanceK = function(root, target, k) {
var adj = {};
adj[root.val] = [];
var stack = [root];
while (stack.length > 0) {
var node = stack.pop();
var kids = [node.left, node.right];
for (var c = 0; c < 2; c++) {
var child = kids[c];
if (child !== null) {
adj[child.val] = [node.val];
adj[node.val].push(child.val);
stack.push(child);
}
}
}
var dist = {};
dist[target] = 0;
var queue = [target], out = [];
for (var h = 0; h < queue.length; h++) {
var u = queue[h];
if (dist[u] === k) { out.push(u); continue; }
for (var i = 0; i < adj[u].length; i++) {
var v = adj[u][i];
if (dist[v] === undefined) { dist[v] = dist[u] + 1; queue.push(v); }
}
}
return out.sort(function(a, b) { return a - b; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)