Find All Binary Tree Nodes Exactly K Edges from a Target Node

You are given a binary tree whose node values are all distinct, the value of a target node, and a non-negative integer k. Return the values of every node whose distance from the target is exactly k, where the distance between two nodes is the number of edges on the path between them. Paths may climb through parents as well as descend into children.

The tree is passed in level order: root[0] is the root, and the remaining entries describe children level by level, left to right. Each non-null node takes the next two entries as its left and right child, with None marking a missing child. None entries never take children of their own, and trailing None values may be omitted.

Function Signature

def nodes_at_distance_k(root: List[Optional[int]], target: int, k: int) -> List[int]:

Rules

• Distance 0 is the target node itself.
• Return the values sorted in ascending order.
• Return an empty list when no node is exactly k edges away.

Constraints

• The tree has between 1 and 10^4 nodes, and root[0] is never None.
• Node values are distinct integers in the range [0, 10^5].
• target is the value of a node in the tree.
• 0 <= k <= 10^4

Examples

Example 1

Input: root = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], target = 5, k = 2
Output: [1, 4, 7]

Node 3 is the root with children 5 and 1; node 5 has children 6 and 2; node 1 has children 0 and 8; node 2 has children 7 and 4. Two edges below 5 reach 7 and 4, and going up to 3 and then down to its right child reaches 1.

Example 2

Input: root = [3, 5, 1, 6, 2, 0, 8, None, None, 7, 4], target = 7, k = 3
Output: [3, 6]

The paths are 7, 2, 5, 3 and 7, 2, 5, 6.

Example 3

Input: root = [1], target = 1, k = 3
Output: []