Rebuild a Binary Tree From Preorder and Inorder Sequences, Returned in Level Order

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

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

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

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

preorder = [7]
inorder  = [7]
Output: [7]

Rebuild a Tree from Preorder and Inorder Traversals

Hints

1. 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?
2. 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.
3. 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.

Approach

The reference builds the tree iteratively. It walks preorder from left to right and keeps a stack holding the path of nodes whose inorder position has not been reached yet, plus a pointer j into inorder. For each new preorder element, if the value on top of the stack is not inorder[j], the stack top has not finished its left subtree, so the new node becomes its left child. Otherwise the stack top's left subtree is complete: the algorithm pops while the stack top equals inorder[j], advancing j each time, and the last popped node receives the new element as its right child. Every node is pushed and popped at most once, so construction is linear and uses no recursion, which matters for a skewed tree of depth 3000. Children are stored as preorder indices in two arrays. Serialization is a breadth-first pass over a queue of node indices, with -1 as the empty marker: a node emits its value and enqueues its left and then its right child, and an empty marker emits an empty entry. Finally the trailing empty entries are removed. The tree is unique because the values are distinct, so the output is unique too.

• Time complexity: O(n)
• Space complexity: O(n)