All Nodes Distance K in Binary Tree

Problem

You are given the root of a binary tree, a reference to one of its nodes called target, and a non-negative integer k. Return the values of every node whose distance from target is exactly k, where distance is the number of edges on the path between the two nodes. Nodes above target count just as much as nodes below it. Any order is acceptable.

• The tree has at most 800 nodes, and all node values are distinct.
• target is always a node that appears somewhere in the tree.
• k is a non-negative integer and may exceed the tree's diameter.

Examples

• root = [8, 4, 2, 9, 6, 1, 5, None, None, 3, 7], target = 4, k = 2 → [2, 3, 7]. Two edges up-and-over (4 → 8 → 2) reach 2; two edges down through 6 reach 3 and 7.
• Same tree, target = 4, k = 0 → [4]. Distance zero is the target itself.
• root = [9], target = 9, k = 3 → []. Nothing is that far away.

Hints

1. Going down from target is a normal traversal. What stops you from going up the same way?
2. If every node knew its parent, the tree would be an undirected graph with at most three neighbours per node. What algorithm finds everything at exactly distance k in such a graph?
3. One DFS to record parent pointers in a map, then BFS from target with a visited set, stopping after k levels.