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.
You can return the answer in any order.
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2 Output: [7,4,1] Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Example 2:
Input: root = [1], target = 1, k = 3 Output: []
Constraints:
[1, 500].0 <= Node.val <= 500Node.val are unique.target is the value of one of the nodes in the tree.0 <= k <= 1000In #863 All Nodes Distance K in Binary Tree, the goal is to find all nodes that are exactly K edges away from a given target node. Since binary tree nodes do not normally store references to their parents, a common strategy is to first convert the tree into an undirected structure.
One effective approach is to perform a DFS traversal to build a parent mapping using a HashMap. This allows movement both downward (to children) and upward (to parent). After building this map, a Breadth-First Search (BFS) starting from the target node explores neighbors level by level until distance K is reached. Nodes discovered at that level form the answer.
An alternative idea is a recursive DFS that calculates the distance from the target while propagating results up the tree. Both strategies ensure every node is visited at most once, leading to efficient performance.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS with Parent Hash Map | O(N) | O(N) |
| DFS Distance Propagation | O(N) | O(N) |
take U forward
In this method, we first traverse the tree to establish a mapping of each node to its parent. This will allow us to easily move upwards in the tree. We then perform a BFS starting from the target node to explore all nodes at distance K. Using a queue to explore nodes level by level ensures we can track the distance from the target correctly.
Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6// Define the TreeNode structure
This C solution first constructs a parent map using DFS to track each node's parent. It then uses BFS to explore nodes at increasing distances from the target node, utilizing a queue to maintain nodes and their distances. The visited array prevents cycles in the tree traversal.
In this method, we perform a DFS from the root to find the path to the target node while also tracking parents of each node. We then use this path to initiate DFS from the target node in all possible directions (left, right, up) to find nodes that are K distance away.
Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack.
1#include <iostream>
2#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void findChildrenAtDistance(TreeNode* node, int K, vector<int>& result, unordered_set<TreeNode*>& visited) {
if (!node || visited.count(node)) return;
if (K == 0) {
result.push_back(node->val);
return;
}
visited.insert(node);
findChildrenAtDistance(node->left, K - 1, result, visited);
findChildrenAtDistance(node->right, K - 1, result, visited);
visited.erase(node);
}
bool findTargetAndParents(TreeNode* root, TreeNode* target, unordered_map<TreeNode*, TreeNode*>& parentMap) {
if (!root) return false;
if (root == target) return true;
parentMap[root->left] = root;
if (findTargetAndParents(root->left, target, parentMap)) return true;
parentMap[root->right] = root;
if (findTargetAndParents(root->right, target, parentMap)) return true;
return false;
}
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
unordered_map<TreeNode*, TreeNode*> parentMap;
vector<int> result;
unordered_set<TreeNode*> visited;
findTargetAndParents(root, target, parentMap);
queue<pair<TreeNode*, int>> bfsQueue;
bfsQueue.push({target, 0});
visited.insert(target);
while (!bfsQueue.empty()) {
auto [node, dist] = bfsQueue.front(); bfsQueue.pop();
if (dist == K) result.push_back(node->val);
for (TreeNode* neighbor : {node->left, node->right, parentMap[node]}) {
if (neighbor && !visited.count(neighbor)) {
visited.insert(neighbor);
bfsQueue.push({neighbor, dist + 1});
}
}
}
return result;
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, DFS can be used by recursively computing the distance from the target node and propagating that information up the tree. When the recursion detects nodes at the required distance, they are added to the result list.
Yes, this problem or similar tree-distance variations have appeared in interviews at top tech companies. It tests understanding of tree traversal, graph conversion, and BFS/DFS problem-solving techniques.
A hash map is typically used to store parent references for each node. Combined with a queue for BFS and a visited set to prevent revisiting nodes, these structures make traversal efficient and manageable.
A common optimal approach is to build a parent pointer map using DFS and then run BFS from the target node. This allows traversal to both children and the parent, effectively treating the tree like an undirected graph. BFS stops once the distance reaches K.
In this C++ implementation, we first fill a parent map while searching the target node. Then initiate a DFS from the target node in all directions, considering kids and parents. We backtrack to ensure each node is only visited once.