All Nodes Distance K in Binary Tree

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Every node in the tree has a different value. The distance between two nodes is the number of edges on the path between them, and that path may go up through parents as well as down through children. Write distance_k(root, target, k) -> list[int] that returns the values of all nodes exactly k edges away from the node whose value is target, in any order. If there are none, return [].

#          8
#        /   \
#       3     10
#      / \      \
#     1   6      14
#        / \     /
#       4   7   13
distance_k(root, 6, 2)    # [1, 8]: up to 3, then down to 1 or up to 8

distance_k(root, 3, 2)    # [4, 7, 10]: down through 6 to 4 and 7, up through 8 to 10
distance_k(root, 14, 0)   # [14]: the target itself
distance_k(root, 1, 7)    # []: nothing is that far from 1

• The tree has between 1 and 131,071 nodes, and target is always one of its values. 0 <= k <= 200,000.
• Trees can be up to 2,100 levels deep. If you recurse, raise the limit first (sys.setrecursionlimit(10_000)), or use an explicit stack.

⭐ Bonus: a speed test on trees of up to 131,071 nodes earns a star in O(n) time.