Rebuild a Binary Tree From Preorder and Inorder Sequences, Returned in Level Order
Company: StackAdapt
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two integer arrays, `preorder` and `inorder`. They are the preorder and inorder traversals of the same binary tree, and all node values in that tree are distinct. Reconstruct the tree and return it in the level-order serialized form defined below.
### Function Signature
```python
def build_tree(preorder: list[int], inorder: list[int]) -> list[int | None]:
```
### Rules
- A preorder traversal visits a node, then its left subtree, then its right subtree. An inorder traversal visits the left subtree, then the node, then the right subtree.
- Because all values are distinct, exactly one binary tree matches the two traversals, so the output is unique.
- **Serialization.** Start with a queue that holds the root. Repeatedly remove the front element:
- if it is a node, append its value to the output, then add its left child and then its right child to the queue, adding an empty marker for any missing child;
- if it is an empty marker, append `None` to the output and add nothing to the queue.
- When the queue is empty, remove every trailing `None` from the output.
### Constraints
- `1 <= len(preorder) == len(inorder) <= 3000`
- Every value is an integer with `-10^9 <= value <= 10^9`, and all values are distinct.
- `inorder` holds exactly the same values as `preorder`, and the two arrays are guaranteed to be the preorder and inorder traversals of one binary tree.
- The tree may be completely skewed, with depth equal to the number of nodes.
### Examples
**Example 1**
```text
preorder = [1, 2, 4, 5, 3, 6]
inorder = [4, 2, 5, 1, 3, 6]
Output: [1, 2, 3, 4, 5, None, 6]
```
The root is 1. Its left subtree has root 2, with children 4 and 5. Its right subtree has root 3, which has no left child and a right child 6.
**Example 2**
```text
preorder = [10, -2, 30]
inorder = [10, 30, -2]
Output: [10, None, -2, 30]
```
The root 10 has no left child and a right child -2. Node 30 is the left child of -2. The trailing `None` markers for the children of 30 and the right child of -2 are removed.
**Example 3**
```text
preorder = [7]
inorder = [7]
Output: [7]
```
Overview: Reconstruct a binary tree with distinct values from its preorder and inorder traversals and return it in level-order form with null markers. Tests how the two traversal orders pin down structure, careful index bookkeeping, and efficient handling of deep, skewed trees.