Example
Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
A tree whose preorder traversal is [3,9,20,15,7]
Reconstruct the tree and verify preorder traversal matches the input preorder.
Full lesson preview
Construct a tree from preorder and inorder
Reconstruct a binary tree given preorder and inorder traversal lists.
Python practice16 minTrees & Binary TreesIntermediateLast updated March 29, 2026
Problem statement
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree's root. You may assume that all values are unique and that the inputs represent a valid binary tree.
Task
Implement build_tree(preorder, inorder) to rebuild the original binary tree using recursion and index mapping for efficiency.
Examples
Input format
A function call build_tree(preorder, inorder) where both arguments are lists of integers.
Output format
Return the root node of the reconstructed binary tree. For tests we provide helper preorder_traversal(root) that returns a list of node values in preorder for verification.
Constraints
- Values in preorder and inorder are unique.
- 0 <= len(preorder) == len(inorder) <= reasonable interview limits.
- The inputs represent a valid binary tree.
Samples
Sample 1
Input
preorder = [1], inorder = [1]
Output
Tree with a single node 1 (preorder traversal [1])
Trivial single-node tree reconstruction.