Katkat
Back

Rebuild a Binary Tree from Two Traversals and Serialize It Level by Level

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given the preorder and inorder traversals of a binary tree with distinct values, rebuild the tree and return its level-order serialization, with empty slots marked as None and trailing ones removed. It tests understanding of traversal orders, careful index bookkeeping and an efficient solution for trees with thousands of nodes, including fully skewed ones.

You are given two integer arrays, preorder and inorder, that hold the preorder and inorder traversals of the same binary tree. Every node value in the tree is distinct. Rebuild the tree and return it serialized in level order.

  • A preorder traversal lists a node, then the preorder traversal of its left subtree, then the preorder traversal of its right subtree.
  • An inorder traversal lists the inorder traversal of a node's left subtree, then the node, then the inorder traversal of its right subtree.

Function Signature

def rebuild_level_order(preorder: list[int], inorder: list[int]) -> list[int | None]:

Rules

  • The two arrays always describe exactly one binary tree. Because the values are distinct, that tree is unique, and so is the output.
  • Serialize the rebuilt tree breadth-first. Start with a queue holding the root and repeatedly remove the entry at the front:
  • if it is a node, append its value to the output, then add its left child and then its right child to the back of the queue, adding an empty slot for each missing child;
  • if it is an empty slot, append None to the output and add nothing to the queue.
  • When the queue is empty, remove every trailing None, so the output always ends with a value.

Constraints

  • 1 <= len(preorder) == len(inorder) <= 3000
  • -10^4 <= preorder[i], inorder[i] <= 10^4
  • All values in preorder are distinct, inorder contains exactly the same values, and the two arrays are the preorder and inorder traversals of one binary tree.
  • The tree may be completely skewed, so its height can be as large as len(preorder).

Examples

Example 1

Input: 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, with children 2 and 3. Node 2 has children 4 and 5; node 3 has no left child and a right child 6. The None marks the missing left child of 3.

Example 2

Input: preorder = [10, -2, 8, 30, 25], inorder = [-2, 8, 10, 25, 30]
Output: [10, -2, 30, None, 8, 25]

Node -2 has only a right child, 8, and node 30 has only a left child, 25. The empty slots for the right child of 30 and for the children of 8 and 25 are trailing, so they are removed.

Example 3

Input: preorder = [5, 4, 3], inorder = [3, 4, 5]
Output: [5, 4, None, 3]

Every node has only a left child, so the tree is a chain of left children.