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:
[1, 500].0 <= Node.val <= 500Node.val are unique.target is the value of one of the nodes in the tree.0 <= k <= 1000In this method, we first traverse the tree to establish a mapping of each node to its parent. This will allow us to easily move upwards in the tree. We then perform a BFS starting from the target node to explore all nodes at distance K. Using a queue to explore nodes level by level ensures we can track the distance from the target correctly.
This C solution first constructs a parent map using DFS to track each node's parent. It then uses BFS to explore nodes at increasing distances from the target node, utilizing a queue to maintain nodes and their distances. The visited array prevents cycles in the tree traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue.
In this method, we perform a DFS from the root to find the path to the target node while also tracking parents of each node. We then use this path to initiate DFS from the target node in all possible directions (left, right, up) to find nodes that are K distance away.
In this C++ implementation, we first fill a parent map while searching the target node. Then initiate a DFS from the target node in all directions, considering kids and parents. We backtrack to ensure each node is only visited once.
Java
Python
C#
JavaScript
Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) using Parent Map | Time Complexity: O(N), where N is the number of nodes, since each node is visited once. Space Complexity: O(N) for storing the parent map and the queue. |
| Depth-First Search (DFS) with Backtracking | Time Complexity: O(N), traversing the tree requires visiting each node once. Space Complexity: O(N) for the parent map and the recursion call stack. |
L30. Print all the Nodes at a distance of K in Binary Tree | C++ | Java • take U forward • 250,522 views views
Watch 9 more video solutions →Practice All Nodes Distance K in Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor