Reconstruct a Binary Tree from Preorder and Postorder Traversals
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given the preorder and postorder traversals of a binary tree whose node values are distinct. Reconstruct one binary tree consistent with both traversals. Some traversal pairs do not identify a unique tree, so the contract below defines a deterministic choice.
## Function Contract
Implement `reconstruct_tree(preorder, postorder)` and return the reconstructed tree as a level-order list. Use `null` for missing children and remove trailing `null` values from the returned list.
## Rules
- The inputs describe the same valid binary tree and contain the same distinct values.
- For an ambiguous node with exactly one child, attach that child on the left.
- For a node with two children, preserve their relative left-to-right order from both traversals.
- The returned tree must reproduce the given preorder and postorder traversals exactly.
- Do not enumerate all possible trees.
## Constraints
- `1 <= len(preorder) == len(postorder) <= 100000`.
- All node values are distinct signed 32-bit integers.
- Account for linear tree depth rather than assuming a balanced tree.
## Examples
```text
preorder = [1, 2, 3]
postorder = [3, 2, 1]
output = [1, 2, null, 3]
```
The traversals are ambiguous; the deterministic rule places each single child on the left.
Overview: Reconstruct one deterministic binary tree from preorder and postorder traversals with distinct values. Preserve both traversals, attach an ambiguous single child on the left, and return a compact level-order representation with explicit missing children where needed.
Read the full ByteDance Software Engineer interview experience this question came from
Given preorder and postorder traversals of the same valid binary tree with distinct signed 32-bit values, reconstruct one consistent tree and return its level-order list. Use null for missing children and remove trailing null values. If a node has exactly one child, attach that child on the left; nodes with two children preserve traversal order. The result must reproduce both inputs, and the algorithm must handle linear depth without enumerating alternatives.
Constraints
- 1 <= len(preorder) == len(postorder) <= 100000.
- Both traversals contain the same distinct signed 32-bit values.
- The traversals describe a valid binary tree.
- An ambiguous single child is attached on the left.
- The returned level-order list uses null for missing children and omits trailing nulls.
- The algorithm must support linear tree depth.
Examples
Input: ([1, 2, 3], [3, 2, 1])
Expected Output: [1, 2, None, 3]
Explanation: Each ambiguous single child is attached on the left.
Input: ([5], [5])
Expected Output: [5]
Explanation: A single traversal value reconstructs one node.
Hints
- Use postorder to recognize when the subtree at the top of a preorder construction stack is complete.
- Filling the left child slot first implements the deterministic one-child rule.