863. All Nodes Distance K in Binary Tree
Problem Description
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.
Examples:
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:
- 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
Python Solution
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
# Build graph representation
graph = defaultdict(list)
def build_graph(node, parent):
if not node:
return
if parent:
graph[node.val].append(parent.val)
graph[parent.val].append(node.val)
build_graph(node.left, node)
build_graph(node.right, node)
build_graph(root, None)
# BFS to find nodes at distance k
queue = deque([(target.val, 0)])
visited = {target.val}
result = []
while queue:
node_val, dist = queue.popleft()
if dist == k:
result.append(node_val)
elif dist < k:
for neighbor in graph[node_val]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return resultImplementation Notes:
- Converts tree to undirected graph for easier traversal
- Uses BFS to find nodes at distance k
- Time complexity: O(n)
- Space complexity: O(n)
Java Solution
class Solution {
Map> graph;
public List distanceK(TreeNode root, TreeNode target, int k) {
// Build graph representation
graph = new HashMap<>();
buildGraph(root, null);
// BFS to find nodes at distance k
Queue queue = new LinkedList<>();
queue.offer(new int[]{target.val, 0});
Set visited = new HashSet<>();
visited.add(target.val);
List result = new ArrayList<>();
while (!queue.isEmpty()) {
int[] current = queue.poll();
int node = current[0], dist = current[1];
if (dist == k) {
result.add(node);
} else if (dist < k) {
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(new int[]{neighbor, dist + 1});
}
}
}
}
return result;
}
private void buildGraph(TreeNode node, TreeNode parent) {
if (node == null) return;
if (!graph.containsKey(node.val)) {
graph.put(node.val, new ArrayList<>());
}
if (parent != null) {
graph.get(node.val).add(parent.val);
if (!graph.containsKey(parent.val)) {
graph.put(parent.val, new ArrayList<>());
}
graph.get(parent.val).add(node.val);
}
buildGraph(node.left, node);
buildGraph(node.right, node);
}
} C++ Solution
class Solution {
unordered_map> graph;
public:
vector distanceK(TreeNode* root, TreeNode* target, int k) {
// Build graph representation
buildGraph(root, nullptr);
// BFS to find nodes at distance k
queue> q;
q.push({target->val, 0});
unordered_set visited;
visited.insert(target->val);
vector result;
while (!q.empty()) {
auto [node, dist] = q.front();
q.pop();
if (dist == k) {
result.push_back(node);
} else if (dist < k) {
for (int neighbor : graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push({neighbor, dist + 1});
}
}
}
}
return result;
}
private:
void buildGraph(TreeNode* node, TreeNode* parent) {
if (!node) return;
if (parent) {
graph[node->val].push_back(parent->val);
graph[parent->val].push_back(node->val);
}
buildGraph(node->left, node);
buildGraph(node->right, node);
}
}; JavaScript Solution
/**
* @param {TreeNode} root
* @param {TreeNode} target
* @param {number} k
* @return {number[]}
*/
var distanceK = function(root, target, k) {
// Build graph representation
const graph = new Map();
function buildGraph(node, parent) {
if (!node) return;
if (!graph.has(node.val)) {
graph.set(node.val, []);
}
if (parent) {
graph.get(node.val).push(parent.val);
if (!graph.has(parent.val)) {
graph.set(parent.val, []);
}
graph.get(parent.val).push(node.val);
}
buildGraph(node.left, node);
buildGraph(node.right, node);
}
buildGraph(root, null);
// BFS to find nodes at distance k
const queue = [[target.val, 0]];
const visited = new Set([target.val]);
const result = [];
while (queue.length) {
const [node, dist] = queue.shift();
if (dist === k) {
result.push(node);
} else if (dist < k) {
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
}
return result;
};C# Solution
public class Solution {
private Dictionary> graph;
public IList DistanceK(TreeNode root, TreeNode target, int k) {
// Build graph representation
graph = new Dictionary>();
BuildGraph(root, null);
// BFS to find nodes at distance k
var queue = new Queue<(int node, int dist)>();
queue.Enqueue((target.val, 0));
var visited = new HashSet { target.val };
var result = new List();
while (queue.Count > 0) {
var (node, dist) = queue.Dequeue();
if (dist == k) {
result.Add(node);
} else if (dist < k) {
if (graph.ContainsKey(node)) {
foreach (var neighbor in graph[node]) {
if (!visited.Contains(neighbor)) {
visited.Add(neighbor);
queue.Enqueue((neighbor, dist + 1));
}
}
}
}
}
return result;
}
private void BuildGraph(TreeNode node, TreeNode parent) {
if (node == null) return;
if (!graph.ContainsKey(node.val)) {
graph[node.val] = new List();
}
if (parent != null) {
graph[node.val].Add(parent.val);
if (!graph.ContainsKey(parent.val)) {
graph[parent.val] = new List();
}
graph[parent.val].Add(node.val);
}
BuildGraph(node.left, node);
BuildGraph(node.right, node);
}
} Implementation Notes:
- Converts binary tree to undirected graph
- Uses BFS with distance tracking
- Time complexity: O(n)
- Space complexity: O(n)