Return all binary search tree keys inside an inclusive range

Given a binary search tree and an inclusive range [low, high], return every key in the tree that lies within the range, in ascending order.

Function Signature

def keys_in_range(root: list[int | None], low: int, high: int) -> list[int]:

Rules

• The tree is given in level order. The first element is the root. Then, for each non-null node in the order it appears, the list gives its left child followed by its right child, with None for a missing child. Trailing None values may be omitted. An empty list is an empty tree.
• All keys are distinct. For every node, every key in its left subtree is smaller than the node's key, and every key in its right subtree is larger.
• A key x is in range when low <= x <= high.
• Return the qualifying keys in strictly ascending order, or an empty list if there are none.

Constraints

• The tree has between 0 and 100000 nodes.
• -10^9 <= key <= 10^9 for every key
• -10^9 <= low <= high <= 10^9
• The tree is not necessarily balanced; its height can equal the number of nodes.

Examples

Example 1

Input: root = [40, 20, 60, 10, 30, 50, 70, None, 15, 25], low = 14, high = 45
Output: [15, 20, 25, 30, 40]

The root 40 has children 20 and 60. Node 20 has children 10 and 30, node 60 has children 50 and 70, node 10 has only a right child 15, and node 30 has only a left child 25. Key 10 is below the range, and keys 50, 60 and 70 are above it.

Example 2

Input: root = [40, 20, 60, 10, 30, 50, 70, None, 15, 25], low = 61, high = 69
Output: []

No key lies between 61 and 69.

Example 3

Input: root = [40, 20, 60, 10, 30, 50, 70, None, 15, 25], low = 50, high = 50
Output: [50]

Both bounds are inclusive, so a range of a single value returns that key when it is present.