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.

For example:

Consider the following binary tree:

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4

If target is node 5 and k is 2, the expected output should be [7, 4, 1].

Here's another example:

Given a binary tree with only one node:

   1

If target is node 1 and k is 3, the expected output should be [] because there are no nodes at distance 3 from node 1.

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # Convert the binary tree to a graph
        graph = defaultdict(list)

        def build_graph(node):
            if not node:
                return
            if node.left:
                graph[node].append(node.left)
                graph[node.left].append(node)
                build_graph(node.left)
            if node.right:
                graph[node].append(node.right)
                graph[node.right].append(node)
                build_graph(node.right)
        
        build_graph(root)
        
        # BFS to find nodes at distance k from target
        queue = deque([(target, 0)])
        visited = {target}
        result = []
        
        while queue:
            node, dist = queue.popleft()
            if dist == k:
                result.append(node.val)
            elif dist < k:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, dist + 1))
        
        return result

Explanation:

1. Build the Graph:

   • The given binary tree is converted into an undirected graph using Depth-First Search (DFS). Each node in the tree becomes a node in the graph, and edges are added between parent and child nodes.

2. Breadth-First Search (BFS):

   • Starting from the target node, a BFS is performed to find all nodes at a distance k.
   • A queue is used to keep track of nodes to visit, along with their distance from the target node.
   • A visited set is used to avoid cycles.
   • When the distance of a node from the target is equal to k, its value is added to the result list.

Example:

Consider the following binary tree:

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4

If target is node 5 and k is 2, the nodes at distance 2 from node 5 are 7, 4, and 1.

Time and Space Complexity:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because:

  • Building the graph takes O(N) time.
  • BFS takes O(N) time in the worst case (when we might visit all nodes).

• Space Complexity: O(N), where N is the number of nodes in the binary tree. This is because:

  • The graph can have up to N nodes and N-1 edges.
  • The queue can contain up to N nodes in the worst case.
  • The visited set can contain up to N nodes.

Edge Cases:

1. Empty Tree:

   • If the root is None, return an empty list.

2. Target Not Found:

   • If the target node is not in the tree, the algorithm will still run, but the result will be an empty list because the BFS will not find any nodes.

3. K = 0:

   • If k is 0, the result should be a list containing only the value of the target node.

4. K > Height of Tree:

   • If k is greater than the maximum possible distance from the target node, the result may be an empty list if there are no nodes at distance k.

Python Code:

from collections import defaultdict, deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        # Convert the binary tree to a graph
        graph = defaultdict(list)

        def build_graph(node):
            if not node:
                return
            if node.left:
                graph[node].append(node.left)
                graph[node.left].append(node)
                build_graph(node.left)
            if node.right:
                graph[node].append(node.right)
                graph[node.right].append(node)
                build_graph(node.right)
        
        build_graph(root)
        
        # BFS to find nodes at distance k from target
        queue = deque([(target, 0)])
        visited = {target}
        result = []
        
        while queue:
            node, dist = queue.popleft()
            if dist == k:
                result.append(node.val)
            elif dist < k:
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, dist + 1))
        
        return result