Quick Overview

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.

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

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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 ```python 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** ```text 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** ```text 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** ```text 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.

Overview: 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. The two arrays always describe exactly one binary tree. Because the values are distinct, that tree is unique, and so is the output. ### Serialization 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. A `None` that is followed by a later value is kept. An empty slot is written `None` in Python, `null` in JavaScript, `null` inside the returned `java.util.List<Integer>` in Java, and `std::nullopt` inside the returned `std::vector<std::optional<int>>` in C++. ### Example 1 ```text 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; the empty slots after 6 are trailing and removed. ### Example 2 ```text 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. The `None` is the missing right child of 5; it is kept because 3 comes after it. ### 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)`. - Every value fits in a 32-bit signed integer (none can exceed 2^31 - 1).

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).
  • Every value fits in a 32-bit signed integer (none can exceed 2^31 - 1).

Examples

Input: ([7], [7])

Expected Output: [7]

Explanation: Minimum valid input: a single node; both of its empty child slots are trailing and removed.

Input: ([-10000], [-10000])

Expected Output: [-10000]

Explanation: Singleton at the lower value bound -10^4.

Hints

  1. The first entry of a preorder listing is the root of the tree it describes, and the same holds for each subtree's own stretch of the listing.
  2. Once you know where a subtree's root sits within its inorder stretch, everything before it belongs to the left subtree and everything after it to the right, and those two parts have the same sizes in both traversals.
  3. A completely skewed tree can be 3000 levels deep, and an empty slot produces None but adds nothing to the queue.

Loading coding console...

Show the approach

Approach

Rebuild the tree in one left-to-right pass over preorder using an explicit stack, then serialize it with a breadth-first queue. Nodes are identified by their position in preorder; lc[i] and rc[i] hold the positions of the left and right children, or -1 for an empty slot.

Reconstruction invariant: the stack holds, deepest on top, the nodes on the current path that have not yet received a right child, and j points at the first inorder value that has not been passed yet. Preorder lists a node's left child immediately after the node, and inorder lists a node's whole left subtree before the node. So when the next preorder value arrives and the top of the stack is not inorder[j], the top still has unfinished left-subtree material, and the new value must be its left child. When the top equals inorder[j], the top's left subtree and the top itself are finished in inorder: pop every node whose value equals the current inorder[j], advancing j each time. The last node popped is the deepest finished node whose right subtree has not started, and the next preorder value is the first node of that right subtree, so it becomes that node's right child. Each position is pushed and popped at most once, so the pass is O(n). It needs no recursion, which matters because a completely skewed tree can be 3000 levels deep, past Python's default recursion limit.

Serialization follows the stated rule literally. Remove the front entry. A node appends its value and enqueues both child slots, using -1 for empty ones; an empty slot appends None and enqueues nothing. The queue receives exactly 2n + 1 entries: the root plus two per node. The last node removed is a leaf, so at least its two empty slots are trailing. Trimming trailing None therefore leaves at most 2n - 1 entries, and every interior None that precedes a later value is kept.

Edge cases: a single node returns just its value; a missing left child before a present right child gives an interior None that must stay; values may be zero or negative, so nodes are indexed by position, never by value; the same preorder with a different inorder describes a different tree.

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