All Nodes Distance K in Binary Tree

def dfs(node, parent):

Define a DFS helper function to assign parent pointers to each node.

This function is the foundation for converting the tree into an undirected graph by linking each node to its parent, enabling upward traversal.

if not node:

Check if the current node is null to terminate recursion.

This base case prevents null pointer exceptions and stops the DFS from traversing beyond leaf nodes.

seen.add(neighbor)

Mark the neighbor as visited.

Adding to the visited set immediately upon enqueueing prevents duplicate entries and cycles.

return

Return immediately if the node is null.

Ensures the recursion unwinds correctly without processing invalid nodes.

node.parent = parent

Assign the parent pointer to the current node.

This assignment creates a backward edge from the current node to its parent, enabling bidirectional traversal.

dfs(node.left, node)

Recursively assign parent pointers to the left subtree.

This recursive call propagates the parent assignment down the left subtree, ensuring all nodes have correct parent references.

dfs(node.right, node)

Recursively assign parent pointers to the right subtree.

Similarly, this call ensures the right subtree nodes are linked to their parents.

dfs(root, None)

Initiate DFS from the root with no parent.

Starting the DFS here sets up the entire tree with parent pointers, with the root having no parent.

queue = deque([target])

Initialize the BFS queue with the target node.

Starting BFS from the target node allows exploration of all nodes at increasing distances.

seen = {target}

Initialize the visited set with the target node to avoid revisiting.

Tracking visited nodes prevents cycles and redundant processing during BFS.

distance = 0

Initialize the distance counter to zero.

This counter tracks how many BFS layers have been expanded, corresponding to the distance from the target.

while queue and distance < k:

Continue BFS while there are nodes to explore and distance is less than k.

This loop condition ensures BFS stops once nodes at distance k are reached or no more nodes remain.

current_length = len(queue)

Record the number of nodes at the current BFS layer.

This count allows processing all nodes at the current distance before incrementing the distance.

for _ in range(current_length):

Iterate over all nodes at the current BFS layer.

Processing nodes layer by layer ensures correct distance tracking.

node = queue.popleft()

Dequeue the next node to process.

Dequeuing nodes in FIFO order maintains BFS's layer-by-layer traversal.

for neighbor in [node.left, node.right, node.parent]:

Iterate over the current node's neighbors: left child, right child, and parent.

Exploring all neighbors ensures BFS covers all possible paths in the undirected graph.

if neighbor and neighbor not in seen:

Check if the neighbor exists and has not been visited.

This condition prevents null pointer errors and avoids revisiting nodes, which could cause infinite loops.

queue.append(neighbor)

Enqueue the neighbor for future BFS processing.

Enqueuing neighbors expands the BFS frontier to the next layer of nodes.

distance += 1

Increment the distance counter after processing the current layer.

This increment reflects moving one step further from the target node in BFS.

return [node.val for node in queue]

Return the values of all nodes currently in the queue, which are at distance k.

After k expansions, the queue contains exactly the nodes at distance k, so their values form the correct output.