Difficulty: MediumTrees

Construct Binary Tree from Preorder and Inorder Traversal

Problem in Plain English

Given preorder and inorder traversal arrays of a binary tree with unique values, rebuild the tree and return its root. The first preorder value is always the current root, and its position in the inorder array splits the left and right subtrees.

Problem Statement

Given integer arrays preorder and inorder, reconstruct their binary tree and return its root. Preorder visits root, then left subtree, then right subtree; inorder visits left subtree, then root, then right subtree. All values are unique, and both arrays are guaranteed to describe the same valid tree.

Create new nodes with the correct left and right links, without changing either input array. Outputs shown here use level-order notation with null placeholders for missing children; the function returns a node, not an array.

Constraints

The traversal arrays each contain between 1 and 3000 values, inclusive, and their lengths are equal.
Every value is between -3000 and 3000, inclusive.
All values are unique, and both arrays contain the same values.
Both arrays are guaranteed valid traversals of the same binary tree.

Examples

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Root 3 splits inorder into left [9] and right [15,20,7]. Preorder supplies 9 for the left leaf and 20 for the right root. Inside that right span, 15 lies left of 20 and 7 lies right, so both become its children.

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]

The single value -1 is the root. Its inorder split leaves both child spans empty, so it is a leaf with null children.

Example 3

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]

Root 1 occurs at the end of inorder, so every remaining value is in its left subtree. The same happens at 2: 3 becomes its left child. Preorder alone would also describe a right chain, but inorder distinguishes the sides.

Example 4

Input: preorder = [2,3,1], inorder = [3,2,1]
Output: [2,3,1]

This is not a binary search tree: 3 is the left child and 1 is the right child. Traversal positions determine the links, not numerical comparisons.

Intuition

Preorder identifies the next subtree root, while inorder tells you which values belong on each side of that root. In Example 1, 3 comes first in preorder; its inorder position separates [9] from [15,20,7]. The left side contains one value, so the next preorder value 9 belongs left and the remaining [20,15,7] belong right. Unique values make every split unambiguous.

Approaches

Naive Recursive Slicing

Solution Details

Reveal Naive Recursive Slicing: intuition, complexity, and code

Intuition

Use the first preorder value as the root, find it by scanning the matching inorder slice, and recursively build copied left and right slices. The split position is also the left subtree size, so it determines exactly how much preorder belongs to the left. This direct method exposes the repeated scanning and copying that the map approach removes.

Step-by-Step Logic

For an empty preorder slice, return null; otherwise create a node from its first value. Example 1 begins with root 3.
Scan the matching inorder slice for that root. Its local index mid is the left subtree size; for 3 it is 1.
Copy the first mid preorder values after the root and the inorder values before the split; recurse on those matching left slices. Example 1 builds the leaf 9 from [9] and [9].
Copy the remaining preorder values and the inorder values after the split; recurse right. Example 1 builds 20 from [20,15,7] and [15,20,7], then builds leaves 15 and 7.
Attach both returned child roots to the fresh node and return it. Example 1 produces [3,9,20,null,null,15,7].

Why It Works

For a nonempty subtree, preorder must begin with its root. Because values are unique, the root has exactly one position in that subtree's inorder span. Values before that position are exactly the left subtree, and values after it are exactly the right subtree. If the root position is mid in a local slice, the left subtree has mid nodes. Thus preorder[1:mid+1] is precisely its root-first sequence, and the remaining preorder slice is precisely the right sequence. Empty spans produce null. Induction on the number of nodes shows that each smaller span is reconstructed correctly; attaching those roots yields the original subtree. The split excludes the current root, so no value is repeated and recursion terminates. Every nonempty call allocates a fresh node and only reads the input arrays.

Dry Run

Naive Recursive Slicing: variable states at each step
Event	Preorder slice	Inorder slice	mid scan / root	Child slices or returned link
enter root	[3,9,20,15,7]	[9,3,15,20,7]	0 to 1 / 3	left [9]/[9]; right [20,15,7]/[15,20,7]
enter left	[9]	[9]	0 / 9	both children []/[]
two empty child calls; return 9	[]	[]	none	return null twice; 3.left = 9
enter right	[20,15,7]	[15,20,7]	0 to 1 / 20	left [15]/[15]; right [7]/[7]
enter 15	[15]	[15]	0 / 15	both children []/[]
two empty calls; return 15	[]	[]	none	return null twice; 20.left = 15
enter 7	[7]	[7]	0 / 7	both children []/[]
two empty calls; return 7	[]	[]	none	return null twice; 20.right = 7
return 20; return 3	completed	completed	none	3.right = 20; [3,9,20,null,null,15,7]

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n^2)

At a subtree of size k, scanning and copying cost O(k). A skewed tree gives sizes n,n-1,...,1, totaling O(n^2) time. Suspended calls retain copied slices along the path, so peak slice storage can also be O(n^2), plus O(h) frames and O(n) output nodes. A balanced tree takes O(n log n) time and O(n) peak storage, but the displayed bounds cover skewed trees. Valid 3000-node chains require a deliberate runtime stack budget: run Java with -Xss16m and Node with --stack_size=16384. The Python entry wrapper temporarily reserves recursion limit 12000 once and restores the prior limit in finally. Verification exercises maximum left, right, and alternating chains under that strategy; the algorithms remain recursive.

Code

Solution.java

1// For depth-3000 inputs, launch with java -Xss16m.2import java.util.Arrays;3import java.util.HashMap;4import java.util.Map;5
6class TreeNode {7    int val;8    TreeNode left, right;9    TreeNode(int val) { this.val = val; }10}11
12class Solution {13    public TreeNode buildTree(int[] preorder, int[] inorder) {14        if (preorder.length == 0) return null;15        TreeNode root = new TreeNode(preorder[0]);16        int mid = 0;17        while (inorder[mid] != preorder[0]) mid++;18        // mid counts left nodes; preorder skips the root before taking them.19        root.left = buildTree(20            Arrays.copyOfRange(preorder, 1, mid + 1),21            Arrays.copyOfRange(inorder, 0, mid));22        root.right = buildTree(23            Arrays.copyOfRange(preorder, mid + 1, preorder.length),24            Arrays.copyOfRange(inorder, mid + 1, inorder.length));25        return root;26    }27}

Hints

Hint 1

The first preorder value is always the root of the subtree being built, so start there.

Hint 2

Find that root inside the inorder array: everything on one side belongs to the left subtree and everything on the other side belongs to the right.

Hint 3

Record inorder positions in a hash map and pass index ranges down the recursion to avoid scanning and slicing on every call.

Edge Cases

A singleton, including a negative value, produces a new leaf with null children.
A root at the first inorder position has no left subtree; a root at the last position has no right subtree. A chain repeats this split at every depth.
A 3000-node left, right, or alternating chain stresses the recursion stack and, for slicing, quadratic copying. Use the stack budget stated with the code.
The tree need not be a binary search tree; Example 4 places 3 left of 2.
All values are unique and traversals are guaranteed valid. Empty ranges inside the recursion are normal even though the public input is nonempty.
Repeated calls must produce independent new nodes and leave both input arrays unchanged; reset the Java map approach cursor on every entry.

Common Mistakes and Interview Tips

Starting the left preorder slice at 0 reuses the root; it must start at 1 and contain exactly mid values.
Using an inorder absolute index as a local left size when implementing slices mixes coordinate systems.
Consuming the right subtree before the left with a shared preorder cursor assigns roots to the wrong spans.
Advancing the cursor for an empty inorder range loses a value; test the base case first.
Comparing values as if rebuilding a BST is incorrect: only traversal positions determine structure.
Claiming O(n) for recursive slicing ignores both repeated scanning and copied arrays; counting only output nodes also misses retained slices.
Assuming default runtime stacks support depth 3000 can fail valid inputs; use the documented launch budget and Python wrapper, or implement an explicit frame stack.

Key Takeaway

Preorder names each subtree root while inorder maps its span, so pairing a root stream with a position map rebuilds divided structures in one pass.