Reconstruct a Binary Tree from Preorder and Postorder Traversals

Quick 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.

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.

Quick Answer: 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.

|Home/Coding & Algorithms/ByteDance
ByteDance logo
ByteDance
Aug 13, 2026, 12:00 AM
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
0
0

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

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...