Nodes Exactly k Edges From a Target

A tree holds distinct integers. Given the value target of one node and a distance k, return the values of all nodes that are exactly k edges away from the target node. Moving up to a parent counts as an edge just like moving down to a child. The values may be returned in any order; return [] if no node qualifies.

Examples

         10
        /  \
       4    15
      / \   / \
     2   6 12  20
        / \
       5   7

Input:  root = build_tree([10, 4, 15, 2, 6, 12, 20, None, None, 5, 7]), target = 4, k = 2
Output: [5, 7, 15]
Explanation: 5 and 7 lie two edges below 4; 15 is reached by going up to 10 and down again.

Input:  root = build_tree([10, 4, 15, 2, 6, 12, 20, None, None, 5, 7]), target = 10, k = 0
Output: [10]

Constraints

• 1 <= number of nodes <= 1000
• 0 <= k <= 1000
• All values are distinct and target is present

Goals

• Turn a tree into an undirected graph by recording each node's parent
• Run a breadth-first search that can move up as well as down