Algorithm

Construct Tree from Preorder and Inorder

Trees Pattern

Construct Binary Tree from Preorder and Inorder Traversal

You are given two arrays holding the same set of values: preorder, the values in the order a pre-order traversal produces them, and inorder, the values an in-order traversal produces. Rebuild the original binary tree and return its root. All values are distinct, and the two arrays are guaranteed to describe one consistent tree — which, given these two orders together, is unique.

CONSTRAINTS
  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • All values in the tree are unique
  • preorder and inorder are guaranteed to be valid traversals of the same tree
EXAMPLE 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Pre-order names 3 as the root; in-order then shows exactly one value (9) sitting before it, so the left subtree holds one node and the remaining three belong on the right.
EXAMPLE 2
Input: preorder = [1,2], inorder = [2,1]
Output: [1,2]
2 appears before 1 in the in-order list, which places it on 1's left. Pre-order alone could not have told these two shapes apart.
EXAMPLE 3
Input: preorder = [1,2], inorder = [1,2]
Output: [1,null,2]
Identical pre-order to the previous case, but now 2 comes after 1 in-order, so it is the right child instead. The in-order array is carrying all the shape information.
EXAMPLE 4
Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
Every value precedes the one before it in-order, which forces a chain leaning entirely to the left.
Why are two traversals needed — is one not enough?
One is not enough. Pre-order [1,2] fits both a left child and a right child, so the shape is ambiguous. In-order pins down which side each value falls on.
Are the values guaranteed unique?
Yes, and the whole approach depends on it: locating the root inside the in-order array requires that value to appear exactly once. With duplicates the input would not even determine a single tree.
Would in-order plus post-order also work?
Yes — post-order's last element is the root instead of pre-order's first. In-order plus *level-order* works too. The one pairing that fails is pre-order plus post-order, which cannot distinguish a lone left child from a lone right child.
Can I assume the input is consistent?
Yes here. Validating that two arrays really describe some tree is a separate, harder question you would want to raise if the guarantee were dropped.

Two readings of one tree, and the job is to rebuild it. Neither reading alone is enough — together they pin down exactly one tree.

One array can't do it, two can

Pre-order [1, 2]: since pre-order is root-then-children, 1 is the root and 2 is its only child. But which side?

text
   1              1
  /       or       \
 2                  2

  both produce pre-order [1, 2]

Pre-order can't separate them. The rescue is a second reading. In-order walks left subtree → node → right subtree, so wherever the root sits in the in-order list, everything before it is the left subtree and everything after is the right.

Two arrays, two jobs

- Pre-order names the root — the first value of the current segment.
- In-order splits the rest — find that root in the in-order segment; values before it go left, values after go right.

text
pre:  [ 3 | 9 | 20 15 7 ]     3 is the root (comes first)
        ^root

in:   [ 9 | 3 | 15 20 7 ]     3 sits here -> LEFT = {9}, RIGHT = {15,20,7}
            ^root

Once in-order says the left side holds k values, pre-order cuts to match: the k values right after the root are the left subtree, the rest are the right. Both arrays split into matching pieces, and each pair is the same problem again → recurse. The root is built before its children, so construction runs top-down.

python
pos = {v: i for i, v in enumerate(inorder)}   # value -> its index in inorder, built once

def build(pre_lo, pre_hi, in_lo, in_hi):      # both ranges inclusive
    if pre_lo > pre_hi:
        return None                            # empty segment -> empty subtree
    root_val = preorder[pre_lo]                # pre-order: root comes first
    root = Node(root_val)
    mid = pos[root_val]                        # in-order: where it splits
    left_size = mid - in_lo                    # how many values on the left
    root.left  = build(pre_lo + 1, pre_lo + left_size, in_lo, mid - 1)
    root.right = build(pre_lo + left_size + 1, pre_hi, mid + 1, in_hi)
    return root

return build(0, len(preorder) - 1, 0, len(inorder) - 1)
Crucial Noteleft_size counts from in_lo, not from 0. Inside a recursive call the in-order segment is a slice, so the root's absolute index mid means nothing on its own — only its offset within the current segment does. Get this wrong and subtrees come out the wrong size.
Finding the root fast

Scanning the in-order segment for each root costs O(N) per node → O(N²). But in-order never changes and every value is unique, so record each value's index once in a hash map up front. Lookups become O(1), and the whole build drops to O(N).

Watch it split

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

text
root 3:   in-order [9 | 3 | 15 20 7]  ->  left {9}, right {15,20,7}
                                                 |
   left  = 9  (leaf)                             |
   right subtree from pre [20 15 7], in [15 20 7]:
        root 20:  in [15 | 20 | 7]  ->  left {15}, right {7}
             left = 15 (leaf), right = 7 (leaf)

result:        3
              / \
             9   20
                /  \
               15   7

Note the pre-order slice [20, 15, 7] gives no clue where 15 and 7 split — it was the in-order slice that said "one value goes left," and only then did pre-order know where to cut. O(N) time, O(N) space.

Interactive Strategy Visualization

Preorder + Inorder

Recursive Slicing Logic

Preorder Pick
3
9
20
15
7
Inorder Slicing
9
3
15
20
7
LEFT SUBTREE
ROOT
RIGHT SUBTREE
Subtree State
Starting construction. Look at first element of preorder.
CODE ANCHOR
rootNode = new Node(preorder[idx++]);
O(N²) Scan In-order For Each Root
→
O(N) Time · O(N) Space Hash Map Index Lookup