Binary Trees Breadth first: level by level
370. All Nodes Distance K in Binary Tree
You are given root, the root node of a binary tree, a node target of the tree, and an integer k. Return
the values of all the nodes whose distance from target is exactly k, in any order.
The distance between two nodes is the number of edges on the path between them. A path can go up from a
node to its parent as well as down to a child. So the parent and the children of a node are all at distance 1
from it, and the node itself is at distance 0. If no node is at distance k, return an empty list.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out. The values in the tree are distinct, so the examples name
target by its value. The outputs list the values from smallest to largest, but any order is accepted.
Example 1
Input: root = [3, 9, -5, 1, 7, null, 2, null, null, 4, 8, null, null, 6]
target = 7
k = 2
[1,3,6]Explanation: Three nodes are two edges from 7. 6 is below it, through 4. 3 is above it, through 9. 1 is reached by going up to 9 and down to its other child.
Example 2
Input: root = [5, 1, 8], target = 8, k = 0
[8]Explanation: The only node at distance 0 from the target is the target itself.
Example 3
Input: root = [0, -1000000000, 1000000000]
target = -1000000000
k = 3
[]Explanation: The farthest node from −1000000000 is 1000000000, two edges away. No node is at distance 3.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- All the values in the tree are distinct.
targetis a node of the tree.0 ≤ k ≤ 105
Clarifying questions
What you would ask an interviewer before writing any code.