Return all binary search tree keys inside an inclusive range
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Given a binary search tree in level-order form and an inclusive range of values, return every key in the tree that falls inside the range, in ascending order. Tests use of the search tree ordering, unbalanced trees, empty results and inclusive boundary handling.
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.
Implement keys_in_range(root, low, high).
Tree encoding and rules:
- The tree is given in level order as the list root. 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 (null in JavaScript and Java, an empty std::optional in C++). 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 (both bounds are inclusive).
- 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.
Every key and bound fits in a 32-bit signed integer; no value can exceed 2^31-1.
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 = 50, high = 50
Output: [50]
Both bounds are inclusive, so a range of a single value returns that key when it is present.
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
Input: ([40, 20, 60, 10, 30, 50, 70, None, 15, 25], 14, 45)
Expected Output: [15, 20, 25, 30, 40]
Explanation: Source example 1: 10 is below the range and 50, 60, 70 are above it.
Input: ([40, 20, 60, 10, 30, 50, 70, None, 15, 25], 61, 69)
Expected Output: []
Explanation: Source example 2: the range falls strictly between adjacent keys 60 and 70.
Hints
- Every non-null entry in the level-order list is a node, and the positions of a node's children follow from the order in which the non-null nodes appear.
- Both bounds are inclusive, and a node outside the range can still have descendants inside it.
- The height can reach 100000, so make sure your traversal does not rely on deep recursion.