All Nodes Distance K In Binary Tree
01 · Problem
You are given the root of a binary tree with distinct values, the value target of one node in the tree, and a non-negative integer k. Return the values of all nodes that are exactly k edges away from the node whose value is target.
Distance is measured along tree edges in any direction, so paths may go up through parents as well as down through children. The answer can be returned in any order. If no node is at that distance, return an empty list. When k = 0, the answer is just the target itself. The tree is given in level-order form, with null marking missing children.
02 · Examples
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
[7,4,1]
Nodes 7 and 4 are two edges below 5 (through 2), and node 1 is two edges away by going up to 3 and then down to 1.
root = [1], target = 1, k = 3
[]
The tree has only one node, so nothing is 3 edges away.
root = [3,5,1,6,2,0,8,null,null,7,4], target = 3, k = 0
[3]
At distance 0 the only node is the target itself.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 500].
- 020 <= Node.val <= 500
- 03All node values are unique.
- 04target is the value of a node in the tree.
- 050 <= k <= 1000
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.