All Nodes Distance K in Binary Tree
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.
Approach 1:
class Solution {
Map> graph;
List answer;
Set visited;
public List distanceK(TreeNode root, TreeNode target, int k) {
graph = new HashMap<>();
buildGraph(root, null);
answer = new ArrayList<>();
visited = new HashSet<>();
visited.add(target.val);
dfs(target.val, 0, k);
return answer;
}
// Recursively build the undirected graph from the given binary tree.
private void buildGraph(TreeNode cur, TreeNode parent) {
if (cur != null && parent != null) {
graph.computeIfAbsent(cur.val, k -> new ArrayList<>()).add(parent.val);
graph.computeIfAbsent(parent.val, k -> new ArrayList<>()).add(cur.val);
}
if (cur.left != null) {
buildGraph(cur.left, cur);
}
if (cur.right != null) {
buildGraph(cur.right, cur);
}
}
private void dfs(int cur, int distance, int k) {
if (distance == k) {
answer.add(cur);
return;
}
for (int neighbor : graph.getOrDefault(cur, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
dfs(neighbor, distance + 1, k);
}
}
}
}
Time Complexity: O(n) and Space Complexity: O(n)
All Nodes Distance K in Binary Tree
The problem of finding All Nodes Distance K in Binary Tree is a popular tree-based challenge that involves identifying nodes located at a specific distance from a given target node. This problem is widely encountered in technical interviews and emphasizes traversal, graph-like thinking, and distance calculations.
Problem Statement
Given the root of a binary tree, a target node, and an integer K, return all the nodes that are exactly K edges away from the target node.
Rules to consider:
- The binary tree is undirected, meaning edges can be traversed in both directions.
- If there are multiple nodes at the same distance, their order in the output does not matter.
- If no nodes exist at distance
K, the output is an empty list.
Approach to Solve the Problem
The problem can be tackled in three main steps:
1. Convert the Tree into a Graph
Since nodes can be traversed in both directions, treat the binary tree as a graph where each node is connected to its parent, left child, and right child. Use an adjacency list to represent this graph.
2. Perform a Breadth-First Search (BFS)
Using the target node as the starting point, perform a level-order traversal (BFS) to identify all nodes at distance K.
3. Handle Edge Cases
Ensure the implementation correctly handles scenarios where:
- The target node is
null. - The binary tree contains only one node.
- No nodes are at distance
K.
Implementation
Here is the Python implementation:
from collections import defaultdict, deque
def distanceK(root, target, K):
# Step 1: Convert Tree into Graph
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)
graph = defaultdict(list)
build_graph(root, None)
# Step 2: Perform BFS from Target Node
visited = set()
queue = deque([(target.val, 0)]) # (node value, current distance)
result = []
while queue:
current, distance = queue.popleft()
if current in visited:
continue
visited.add(current)
if distance == K:
result.append(current)
elif distance < K:
for neighbor in graph[current]:
queue.append((neighbor, distance + 1))
return result
Here is a Java implementation:
import java.util.*;
class Solution {
Map> graph = new HashMap<>();
public List distanceK(TreeNode root, TreeNode target, int K) {
buildGraph(root, null);
return bfs(target, K);
}
private void buildGraph(TreeNode node, TreeNode parent) {
if (node == null) return;
graph.putIfAbsent(node, new ArrayList<>());
if (parent != null) {
graph.get(node).add(parent);
graph.get(parent).add(node);
}
buildGraph(node.left, node);
buildGraph(node.right, node);
}
private List bfs(TreeNode target, int K) {
Queue queue = new LinkedList<>();
Set visited = new HashSet<>();
queue.offer(target);
visited.add(target);
int distance = 0;
while (!queue.isEmpty()) {
if (distance == K) {
List result = new ArrayList<>();
for (TreeNode node : queue) {
result.add(node.val);
}
return result;
}
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode current = queue.poll();
for (TreeNode neighbor : graph.get(current)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
distance++;
}
return new ArrayList<>();
}
}
Example
Consider the binary tree:
Tree Structure:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
If the target node is 5 and K = 2, the nodes at distance 2 are:
[7, 4, 1]
Complexity Analysis
Time Complexity: O(n), where n is the number of nodes in the tree. The graph construction and BFS traversal each take O(n).
Space Complexity: O(n), due to the adjacency list and BFS queue.
Applications
- Tree-based queries in database systems.
- Network analysis, such as finding devices within a certain hop distance.
- Visualizing relationships in hierarchical data structures.
Conclusion
The problem of finding all nodes at distance K from a target node in a binary tree is an excellent exercise in understanding the interplay between trees and graphs. By converting the tree into a graph and using BFS, we can efficiently solve the problem while gaining deeper insights into traversal and distance calculations.
Try experimenting with different graph representations and traversal techniques to optimize performance and handle edge cases gracefully.
