All Nodes Distance K in Binary Tree
Last Updated: April 5, 2026
Understanding the Problem
We have a binary tree and a target node somewhere inside it. We need to find every node whose distance from the target is exactly k. Distance here means the number of edges on the path between two nodes.
The tricky part is that distance can go in any direction. A node at distance k from the target could be k levels down in the target's subtree, or it could be up through the target's parent and then down some other branch. In a regular binary tree, nodes only have pointers to their children, not to their parents. So moving "upward" from the target isn't straightforward.
This is what makes the problem interesting. If we could only move downward, a simple DFS from the target going k levels deep would do the job. But we also need to reach nodes that are "above" the target or in completely different subtrees. The core challenge is figuring out how to traverse upward in a tree that only gives us downward pointers.
Key Constraints:
Number of nodes in range [1, 500]- With at most 500 nodes, even an O(n^2) approach would be fine. But all natural approaches here are O(n), so this constraint just tells us we don't need to worry about performance.0 <= Node.val <= 500, all values unique- Unique values mean we can use node values as keys in a hash map. This lets us identify nodes unambiguously.0 <= k <= 1000- k can be larger than the tree's height. If no node exists at distance k, we just return an empty list.
Approach 1: Parent Map + BFS
Intuition
The first thing that jumps out is the "distance" part. In trees, we usually think about depth (distance from the root), but here we need distance from an arbitrary node. Distance k from the target means we need to go exactly k edges in any direction, including upward toward the root.
A binary tree only has downward pointers (left and right children). But if we could also go upward, the tree would behave like an undirected graph, and finding all nodes at distance k would just be BFS radiating outward from the target for k levels.
So here's the plan: first, do a DFS over the tree to build a map from each node to its parent. This gives us the "upward" pointers we're missing. Then, starting from the target node, do a BFS that expands in three directions at each step: left child, right child, and parent. After exactly k levels of BFS, every node in the current frontier is at distance k from the target.
We need a visited set to avoid revisiting nodes. Without it, we'd bounce back and forth between a node and its parent forever.
Algorithm
- Do a DFS over the entire tree to build a hash map mapping each node to its parent node. The root's parent is null.
- Initialize a queue with the target node, and a visited set containing the target node.
- Run BFS for exactly k levels:
- For each node in the current level, check its left child, right child, and parent.
- If any of these neighbors exist and haven't been visited, add them to the queue and mark them as visited.
- After k levels of BFS, every node remaining in the queue is at distance k from the target. Collect their values.
Example Walkthrough
Code
- Time Complexity: O(n). Building the parent map visits every node once. The BFS also visits each node at most once. Total: O(n).
- Space Complexity: O(n). The parent map stores one entry per node. The visited set and queue can hold up to n nodes. Overall: O(n).
This approach is clean and intuitive but uses two passes over the tree. What if we replaced BFS with DFS for a recursive alternative?
Approach 2: Parent Map + DFS
Intuition
This approach uses the same parent map idea but replaces BFS with DFS. After building the parent map, we start a DFS from the target node. At each step, we track the current distance. When the distance equals k, we add the node to the result. We expand to three neighbors (left child, right child, parent), using a visited set to avoid cycles.
The key observation is the same: once we have parent pointers, the tree becomes an undirected graph, and both BFS and DFS can find nodes at a specific distance.
Algorithm
- Build a parent map by traversing the entire tree (same as Approach 1).
- Starting from the target node, run a DFS with parameters: current node, current distance, visited set.
- If the current distance equals k, add the node's value to the result and return.
- For each neighbor (left child, right child, parent), if it exists and hasn't been visited, mark it as visited and recurse with distance + 1.
Example Walkthrough
Code
- Time Complexity: O(n). Building the parent map: O(n). The DFS visits each node at most once: O(n). Total: O(n).
- Space Complexity: O(n). Parent map: O(n). Visited set: O(n). Recursion stack: O(n) worst case. Total: O(n).
Both approaches so far need a parent map. Can we eliminate it entirely by using the recursion stack to implicitly track the path from root to target?
Approach 3: Single DFS (No Parent Map)
Intuition
Instead of building a parent map and then doing a second traversal, we do everything in a single DFS from the root. The key insight is that the recursive call stack naturally knows the path from the root to the current node. If we find the target during our DFS, we can use the return value to communicate the distance back up the call chain.
Our DFS function returns the distance from the current node to the target (if the target is in the current node's subtree), or -1 otherwise. When a node learns that the target is at distance d in its left subtree, it knows that any node at distance k-d-2 in its right subtree is at distance k from the target. So it does a secondary DFS into the right subtree looking for nodes at that specific depth.
The formula k-d-2 comes from: the target is d edges below the left child, the current node is 1 edge above the left child, and the right child is 1 edge below the current node. So total distance = d + 1 + 1 + x = d + 2 + x. Setting d + 2 + x = k gives x = k - d - 2.
Algorithm
- Define a helper function
findDown(node, depth)that collects all nodes at exactlydepthlevels belownode. - Define the main DFS function
dfs(node)that returns the distance fromnodeto the target, or -1 if the target isn't innode's subtree. - In
dfs(node): - If
nodeis the target, callfindDown(node, k)to collect nodes k levels below the target. Return 0. - Recurse on the left child. If it returns distance d (not -1), the current node is at distance d+1 from target. If d+1 == k, add current node to result. Otherwise, search the right subtree for nodes at depth k-d-2.
- Mirror logic for the right child.
- If neither child contains the target, return -1.
- Call
dfs(root)and return the result.
Example Walkthrough
Code
- Time Complexity: O(n). The main DFS visits each node at most once. The findDown calls collectively visit each node at most once. Total: O(n).
- Space Complexity: O(n). The recursion stack can go as deep as the tree height: O(h), which is O(n) for a skewed tree. No extra data structures besides the result list.