The ring around a node
List all nodes exactly k edges from a target node, in any direction, by recording each node's parent and spreading out one ring at a time. About 20 minutes.
Give every node a way up
A node in a binary tree knows its two children but not its parent. For a question about distance in every direction, you need to move up as well. So walk the whole tree once, and record in a map each node's parent. The root's parent is nothing.
While walking, also remember which node holds the target value, since that is where the spread starts.
parent = {}
parent[child] = node # a way up- ring
- 5
Ring 0 is the target 5 alone.
Spread out ring by ring
Now each node has up to three neighbours: left, right and parent. Start with the target alone as the first ring. To get the next ring, collect all unvisited neighbours of the current ring, and mark them visited.
After k rounds, the current ring holds exactly the nodes k edges from the target. Visited marks matter, because a child's parent is the node you just came from. Sort the values for a stable answer.
frontier = [target]
seen = {target}
steps = 0
steps += 1 # one ring outWhy must visited nodes be marked in the spread?
- ABecause a child can step back to its parent, the node it came from
- BTo make the spread faster
- CTo keep the answer sorted
Show the answer
Because a child can step back to its parent, the node it came from. Without marks the spread would bounce between neighbours and give wrong rings.
All nodes distance k from a node
Given the root of a binary tree whose node values are all different, the value target of a node in the tree, and an integer k, return the values of all nodes that are exactly k edges away from the target node, in increasing order. Distance counts edges in any direction, up or down.
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], target = 5, k = 2 → [1, 4, 7]
1 ≤ number of nodes ≤ 500 · all values are different · target is in the tree · 0 ≤ k ≤ 1,000