531. All Nodes Distance K in Binary Tree
You are given the root of a binary tree whose node values are all distinct, an integer target that is guaranteed to be the value of some node in the tree, and a non-negative integer k.
The distance between two nodes is the number of edges on the path between them — and paths may travel upward through parents as well as down through children.
Return the values of every node whose distance from the target node is exactly k, sorted in increasing order. If no node is exactly k edges away, return an empty list. (With k = 0 the answer is the target itself.)
The tree arrives in level order, with null marking a missing child.
Example 1:
Input: root = [1, 2, 3, 4, 5, null, 6, null, null, 7, 8], target = 2, k = 2
Output: [3, 7, 8]
Explanation: One edge from node 2 reaches its parent 1 and its children 4 and 5. A second edge reaches 3 (down the other side of the root) and 7 and 8 (below 5). Sorted: [3, 7, 8].
Example 2:
Input: root = [1, 2, 3], target = 1, k = 1
Output: [2, 3]
Explanation: Both children of the root sit exactly one edge away from it.
Constraints:
- 1 ≤ number of nodes ≤ 500
- 0 ≤ Node.val ≤ 500, and all node values are distinct
- target is guaranteed to be the value of a node in the tree
- 0 ≤ k ≤ 1000
Hints:
Tree edges only point downward, but distance ignores direction. If every node also knew its parent, the tree would just be a graph — and "everything at distance exactly k" is a textbook BFS: expand k layers from the target.
One DFS can record each node's parent in a hash map (or build a full adjacency list keyed by value, since values are unique). Then BFS from the target with a visited set so the search never walks back the way it came.
There is also a no-graph version: write a DFS that returns each node's distance to the target (or -1 if the target isn't in its subtree). An ancestor at distance d < k then dives its *other* subtree collecting nodes exactly k − d − 1 levels deeper.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, 5, null, 6, null, null, 7, 8], target = 2, k = 2
Expected output: [3, 7, 8]