All Nodes Distance K in Binary Tree
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.
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
Input: root = , target = 1, k = 3
- The number of nodes in the tree is in the range
0 <= Node.val <= 500
- All the values
targetis the value of one of the nodes in the tree.
0 <= k <= 1000
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
Let’s see how we might implement this functionality:
- Initialize the Dictionary.
- Perform DFS on the root node and add every node’s parents and children to the Dictionary.
- To perform BFS take a Queue and visited hash to track the processed nodes.
- Add the target node into the queue to start BFS from the target node.
- During iteration, we will get all the parents and children nodes of the current node and mark them as visited and processed.
- 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:
- Time Complexity: O(N), where N is the number of nodes in the given tree.
- Space Complexity: O(N).