Return Binary Search Tree Values in Ascending Order
Company: Moodys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Return Serialized BST Values in Ascending Order
Implement `ascendingBstValues(levelOrder) -> values`.
`levelOrder` is a JSON-compatible array containing signed 32-bit integers and `null`. It serializes a binary search tree in breadth-first order using this exact rule:
1. An empty tree is encoded as `[]`.
2. A nonempty encoding begins with the integer root value.
3. Starting with the root in a queue, remove one non-null node at a time. The next array element, if present, is its left child and the following element, if present, is its right child. A `null` denotes a missing child and is not added to the queue.
4. Missing elements at the end mean that the remaining child positions are `null`. Trailing `null` elements are omitted, and the input contains no elements after the node queue becomes empty.
The decoded tree is guaranteed to be a valid binary search tree: values in a node's left subtree are no greater than the node value, and values in its right subtree are no smaller. Duplicate values represent distinct nodes.
Return every node value exactly once in nondecreasing order. Do not mutate `levelOrder`. The implementation must handle a highly skewed tree without relying on recursion depth proportional to the number of nodes.
### Constraints
- `0 <= levelOrder.length <= 200,000`.
- The number of non-null elements is at most 100,000.
- Every non-null value is between `-2,147,483,648` and `2,147,483,647`.
- The result must contain exactly one value per non-null input element.
- Expected traversal time is `O(n)`, where `n` is the number of tree nodes; deserialization and auxiliary traversal storage must also be `O(n)` or better.
```hint Separate the two invariants
First make the queue-based decoding rule unambiguous; then choose a traversal whose ordering follows from the BST property and whose control state is safe for a skewed tree.
```
### Examples
```text
levelOrder = [2, 1, 3]
values = [1, 2, 3]
```
```text
levelOrder = [2, 2, 5, null, null, 4]
values = [2, 2, 4, 5]
```
```text
levelOrder = [3, 2, null, 1]
values = [1, 2, 3]
```
```text
levelOrder = []
values = []
```
### Discussion Requirements
- Explain why a recursive traversal can exhaust the call stack when the BST is very large or highly skewed, even though its total running time is linear.
- Explain why merely increasing the process or thread stack size only moves the failure threshold, consumes additional memory per active call, and depends on deployment-specific limits rather than removing the depth risk.
- Compare an iterative traversal with an explicit stack, which uses `O(h)` auxiliary space for tree height `h`, with Morris traversal, which uses `O(1)` auxiliary traversal space by temporarily changing pointers.
- For Morris traversal, state that every temporary pointer must be restored before the function returns. Distinguish traversal auxiliary space from the required `O(n)` output array.
Quick Answer: Decode a breadth-first binary-search-tree representation and return every stored value in nondecreasing order. This task evaluates precise deserialization, duplicate preservation, iterative traversal of highly skewed trees, complexity accounting, and trade-offs in auxiliary space.
Implement `ascendingBstValues(levelOrder) -> values`.
`levelOrder` is an array containing signed 32-bit integers and `null` (`None` in Python, `null` in JavaScript and Java, an empty `std::optional<int>` in C++). It serializes a binary search tree in breadth-first order using this exact rule:
1. An empty tree is encoded as `[]`.
2. A nonempty encoding begins with the integer root value.
3. Starting with the root in a queue, remove one non-null node at a time. The next array element, if present, is its left child and the following element, if present, is its right child. A `null` denotes a missing child and is not added to the queue.
4. Missing elements at the end mean that the remaining child positions are `null`. Trailing `null` elements are omitted, and the input contains no elements after the node queue becomes empty.
The decoded tree is guaranteed to be a valid binary search tree: values in a node's left subtree are no greater than the node value, and values in its right subtree are no smaller. Duplicate values represent distinct nodes.
Return every node value exactly once in nondecreasing order. The returned array therefore contains exactly one entry per non-null element of `levelOrder`, sorted from smallest to largest, and every input has exactly one correct answer. Return an empty array for the empty tree. Do not mutate `levelOrder`. The implementation must handle a highly skewed tree without relying on recursion depth proportional to the number of nodes.
### Examples
Example 1
```text
levelOrder = [2, 1, 3]
values = [1, 2, 3]
```
The root is `2`; its left child is `1` and its right child is `3`.
Example 2
```text
levelOrder = [2, 2, 5, null, null, 4]
values = [2, 2, 4, 5]
```
The root `2` has left child `2` and right child `5`. The two `null` elements are the left child's absent children, so `4` is the left child of `5`. Both nodes valued `2` are distinct, so `2` appears twice in the answer.
Example 3
```text
levelOrder = [3, 2, null, 1]
values = [1, 2, 3]
```
The root `3` has left child `2` and no right child. The array then ends after `1`, the left child of `2`; the omitted trailing element means `2` has no right child.
Example 4
```text
levelOrder = []
values = []
```
### Follow-up discussion
Be ready to explain why a recursive in-order traversal can exhaust the call stack on a very large or highly skewed BST even though its total running time is linear; why raising the process or thread stack size only moves the failure threshold, costs extra memory per active call, and depends on deployment-specific limits rather than removing the depth risk; and how an iterative traversal with an explicit stack (`O(h)` auxiliary space for height `h`) compares with Morris traversal, which uses `O(1)` auxiliary traversal space by temporarily rewiring pointers that must all be restored before the function returns. Auxiliary traversal space is counted separately from the required `O(n)` output array.
Constraints
- 0 <= levelOrder.length <= 200,000
- The number of non-null elements is at most 100,000
- Every non-null value is between -2,147,483,648 and 2,147,483,647
- levelOrder always encodes a valid binary search tree by the rule above: values in a node's left subtree are no greater than the node value and values in its right subtree are no smaller
- The result must contain exactly one value per non-null input element, in nondecreasing order
- Expected traversal time is O(n), where n is the number of tree nodes; deserialization and auxiliary traversal storage must also be O(n) or better
Examples
Input: ([],)
Expected Output: []
Input: ([7],)
Expected Output: [7]
Hints
- Decode before you traverse. Keep a queue of nodes that still need their two child slots and walk the array left to right: the next element is the left child, the one after it is the right child, and a null child is simply never enqueued.
- The array can stop before every queued node has been given two child slots. Treat a missing element the same way you treat an explicit null rather than as malformed input.
- The BST property already fixes the answer's order, so the only real decision is where the traversal keeps its control state. Put it in a structure you allocate yourself instead of in the call stack, and a 100,000-node chain costs no depth.