All Nodes Distance K in Binary Tree

All Nodes Distance K in Binary Tree

What is this problem about?

The "All Nodes Distance K in Binary Tree interview question" is a popular graph-traversal problem. You are given a binary tree, a "target" node, and an integer k. You need to find all nodes that are exactly distance k from the target. In a standard tree, you can easily find descendants at distance k, but finding ancestors or nodes in other branches is harder because edges in a tree typically only point downwards.

Why is this asked in interviews?

This is a classic "All Nodes Distance K in Binary Tree coding problem" asked by companies like Google, Microsoft, and Amazon. It tests a candidate's ability to transform a data structure (a tree) into something more flexible (a graph). It evaluates knowledge of Breadth-First Search (BFS) and the ability to manage parent pointers or bidirectional mapping.

Algorithmic pattern used

This problem relies on the Breadth-First Search (BFS) and Graph Conversion patterns.

1. Annotate Parents: Perform a DFS to map every node to its parent. This effectively turns the directed tree into an undirected graph.
2. Layer-by-Layer Search: Start a BFS from the target node.
3. Distance Tracking: Keep track of the distance from the target. When you reach distance k, the nodes in the current queue are your answer.
4. Avoid Cycles: Use a "visited" set to ensure you don't go back and forth between a node and its parent.

Example explanation

Imagine a tree where 5 is the root, 3 is the left child, and 2 is the left child of 3. Target is node 3, $K=1$.

1. Parents: Node 3's parent is 5. Node 2's parent is 3.
2. BFS Start: Queue = [3], Distance = 0.
3. BFS Distance 1: Move from 3 to its neighbors: 2 (left child), 5 (parent). Queue = [2, 5].
4. Output: [2, 5] because they are exactly distance 1 from node 3.

Common mistakes candidates make

• Only looking down: Forgetting that the distance $k$ can lead "up" the tree to the parent and then "down" into other subtrees.
• Cycle Loops: Not using a visited set, leading to an infinite loop between a child and its parent during BFS.
• Node vs Value: Confusion between searching for a node's value and the actual node object/reference.

Interview preparation tip

Practice "graphifying" a tree. Many tree problems become simpler if you treat them as undirected graphs. BFS is the standard way to find nodes at a specific distance in an unweighted graph, so make sure you are comfortable implementing it from scratch.