Katkat
Back

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

StackAdaptMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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]