Binary Tree · Construction
Visual EditorTree Problems

Construct Binary Tree from Inorder and Postorder

Build root from postorder tail, split by inorder, then recurse right-first and left-second.

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

Problem Statement

Given inorder and postorder arrays of distinct values, reconstruct the original binary tree.

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

01 · Full Diagram

3207159

02 · Array Split Visualization

Step 1: pick root 3 (postorder pointer=4)

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

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

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

Step 3: pick root 7 (postorder pointer=2)

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

Step 4: pick root 15 (postorder pointer=1)

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

Step 5: pick root 9 (postorder pointer=0)

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

03 · Dry Run Grid

Step
Pointer
Partial Tree
1
post[4]
root=3, recurse right then left
2
post[3]
root=20, recurse right then left
3
post[2]
root=7, recurse right then left
4
post[1]
root=15, recurse right then left
5
post[0]
root=9, recurse right then left

04 · Code

def buildTree(inorder, postorder):
    idx = {v: i for i, v in enumerate(inorder)}
    post_i = len(postorder) - 1

    def build(l, r):
        nonlocal post_i
        if l > r:
            return None
        root_val = postorder[post_i]
        post_i -= 1
        root = TreeNode(root_val)
        mid = idx[root_val]
        root.right = build(mid + 1, r)
        root.left = build(l, mid - 1)
        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