Binary Tree · Construction

Construct Binary Tree from Inorder and Preorder

Build root from preorder pointer and split exact subtree ranges using inorder index positions.

Key concepts at a glance — for those who already know the basics.

Problem Statement

Given preorder and inorder arrays of distinct values, construct and return the binary tree.

preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] -> root=3

01 · Full Diagram

02 · Array Split Visualization

Step 1: pick root 3 (preorder pointer=0)

inorder window [9, 3, 15, 20, 7] -> left [9], right [15, 20, 7]

Step 2: pick root 9 (preorder pointer=1)

inorder window [9] -> left [], right []

Step 3: pick root 20 (preorder pointer=2)

inorder window [15, 20, 7] -> left [15], right [7]

Step 4: pick root 15 (preorder pointer=3)

inorder window [15] -> left [], right []

Step 5: pick root 7 (preorder pointer=4)

inorder window [7] -> left [], right []

03 · Dry Run Grid

Step

Pointer

Partial Tree

pre[0]

root=3, split by inorder

pre[1]

root=9, split by inorder

pre[2]

root=20, split by inorder

pre[3]

root=15, split by inorder

pre[4]

root=7, split by inorder

04 · Code

def buildTree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    pre_i = 0

    def build(l, r):
        nonlocal pre_i
        if l > r:
            return None
        root_val = preorder[pre_i]
        pre_i += 1
        root = TreeNode(root_val)
        mid = idx[root_val]
        root.left = build(l, mid - 1)
        root.right = build(mid + 1, r)
        return root

    return build(0, len(inorder) - 1)

05 · Final Preview

Constructed tree: root 3, left 9, right 20 with children 15 and 7.

Ready to see it in action?

Step through the visualizer to watch the algorithm state update live.

Open Visualizer