How do you solve All Nodes Distance K in Binary Tree on LeetCode?

All Nodes Distance K in Binary Tree (LeetCode #863) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding tree traversal is crucial for solving tree problems.

What is the brute force solution for All Nodes Distance K in Binary Tree?

The brute force approach for All Nodes Distance K in Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves finding the target node and then performing a BFS or DFS from that node to find all nodes at distance k. This is straightforward but inefficient because we may traverse the tree multiple times. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for All Nodes Distance K in Binary Tree?

Explain your thought process clearly while coding. Consider edge cases and discuss them with the interviewer. Practice building tree structures and traversing them.

What are common mistakes when solving All Nodes Distance K in Binary Tree?

Not handling edge cases like k being larger than the tree height. Forgetting to mark nodes as visited, leading to infinite loops.

#863

All Nodes Distance K in Binary Tree

Medium

Hash TableTreeDepth-First SearchBreadth-First SearchBinary TreeHash MapGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a single DFS to build a graph representation of the tree, allowing us to easily traverse to find nodes at distance k from the target without redundant traversals.

⚙️

Algorithm

3 steps

1Step 1: Build a graph representation of the tree using a DFS.
2Step 2: Perform a BFS from the target node to find all nodes at distance k.
3Step 3: Return the values of the nodes found.

solution.py39 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def distanceK(self, root: TreeNode, target: int, k: int):
10        graph = {}
11        self.build_graph(root, None, graph)
12        return self.bfs(graph, target, k)
13
14    def build_graph(self, node, parent, graph):
15        if not node:
16            return
17        if parent:
18            graph.setdefault(node.val, []).append(parent.val)
19            graph.setdefault(parent.val, []).append(node.val)
20        self.build_graph(node.left, node, graph)
21        self.build_graph(node.right, node, graph)
22
23    def bfs(self, graph, target, k):
24        from collections import deque
25        queue = deque([target])
26        visited = {target}
27        distance = 0
28
29        while queue:
30            if distance == k:
31                return list(queue)
32            for _ in range(len(queue)):
33                node = queue.popleft()
34                for neighbor in graph[node]:
35                    if neighbor not in visited:
36                        visited.add(neighbor)
37                        queue.append(neighbor)
38            distance += 1
39        return []

ℹ

Complexity note: The time complexity is O(n) because we visit each node once to build the graph and once more to perform BFS. The space complexity is also O(n) due to the graph representation.

1Understanding tree traversal is crucial for solving tree problems.
2Graph representation can simplify traversal problems in trees.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.