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.
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.
### 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 an empty entry to the output and add nothing to the queue.
- When the queue is empty, remove every trailing empty entry from the output.
- The empty entry is `None` in Python, `null` in JavaScript, a `null` element of the returned `List<Integer>` in Java, and `std::nullopt` in the returned `std::vector<std::optional<int>>` in C++.
### 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.
Every value fits in a signed 32-bit integer, and no computation needs values outside that range.
### 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 empty entries for the children of 30 and the right child of -2 are removed.
**Example 3**
```text
preorder = [7]
inorder = [7]
Output: [7]
```
Constraints
- 1 <= len(preorder) == len(inorder) <= 3000
- -10^9 <= value <= 10^9 for every value, 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
Input: ([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6])
Expected Output: [1, 2, 3, 4, 5, None, 6]
Input: ([10, -2, 30], [10, 30, -2])
Expected Output: [10, None, -2, 30]
Hints
- The first element of preorder is always the root. Where does that value sit in inorder, and what does everything to its left and right represent?
- Scanning inorder for the root at every step can cost O(n^2). Precompute a value-to-index map, or walk both arrays with a stack so each node is pushed and popped once.
- A skewed tree can be 3000 levels deep, so recursion may overflow some language stacks. An explicit stack avoids that, and the level-order output needs a plain queue that also records empty children.