All Nodes Distance K in Binary Tree
Medium · Trees · Hash Table · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
You are given the root of a binary tree whose values are all different, a node target of that tree, and an integer k.
Return the values of every node exactly k edges away from target. Distance is counted along tree edges, so a path may go up through parents as well as down through children. The values may be returned in any order.
The tests give the tree in level order (None for a missing child) and the target by its value; they build the tree and find the target node for you.
Examples
Input: root = [1,2,3,4,5,6,7], target = 2, k = 2 Output: [3]
Up from 2 to 1, then down to 3: two edges. 2's own children are only one edge away.
Input: root = [1,2,3,4,5,6,7], target = 4, k = 3 Output: [3]
The path 4 → 2 → 1 → 3 has three edges; 6 and 7 are four away.
Input: root = [1,2], target = 2, k = 0 Output: [2]
At distance zero the only node is the target itself.
Constraints
- 1 <= number of nodes <= 500
- 0 <= Node.val <= 500
- all values are different
- target is a node of the tree
- 0 <= k <= 1000
Approaches
- Baseline: distance to every node through its common ancestor — time O(n · h), space O(n · h)
Follow-up
Can you do it without a parent map? A recursive walk can return the distance from each subtree to the target; on the way back up, each ancestor at distance d collects the nodes k - d - 1 levels down its other side. It uses only the recursion stack.
Related problems
Start free on Cariara · Coding problems · System design studio
