Introduction

In this blog post, we will explore how to solve the LeetCode problem "863" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: 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

Explanation

Here's the breakdown of the solution:

• Convert Tree to Graph: Represent the tree as an undirected graph where each node is connected to its parent and children. This allows us to traverse the tree in any direction.
• Breadth-First Search (BFS): Perform BFS starting from the target node to find all nodes at distance k.

• Track Visited Nodes: Keep track of visited nodes to avoid cycles during the BFS traversal.

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

Code

    from collections import defaultdict, deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def distanceK(root, target, k):
    """
    Finds all nodes that are a distance k from the target node in a binary tree.

    Args:
        root: The root of the binary tree.
        target: The target node (TreeNode object).
        k: The distance k.

    Returns:
        A list of the values of all nodes that are a distance k from the target node.
    """

    graph = defaultdict(list)

    def build_graph(node, parent):
        if node:
            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)

    queue = deque([(target.val, 0)])
    visited = {target.val}
    result = []

    while queue:
        node_val, distance = queue.popleft()

        if distance == k:
            result.append(node_val)
        elif distance < k:
            for neighbor in graph[node_val]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, distance + 1))

    return result