All Nodes Distance K in Binary Tree

Photo by Adrien Robert on Unsplash

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

Solution

We can solve this problem using a combination of DFS and BFS algorithms. First, we’ll do a DFS on the tree and store every node’s parent and children in a Dictionary. After, we do a Breadth First Search to find all nodes a distance K from the target.

Let’s see how we might implement this functionality:

1. Initialize the Dictionary.
2. Perform DFS on the root node and add every node’s parents and children to the Dictionary.
3. To perform BFS take a Queue and visited hash to track the processed nodes.
4. Add the target node into the queue to start BFS from the target node.
5. During iteration, we will get all the parents and children nodes of the current node and mark them as visited and processed.
6. When the k value reach 0, you’ll have the nodes that are k distance from the target node as the result.

Let’s look at the code for the solution:

Complexity Analysis

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