Constructing Binary Trees from Traversal Sequences

Given two traversal sequences of a binary tree, can you reconstruct the original tree? This is one of the most elegant recursive problems in DSA. The key insight is that preorder tells you the root, and inorder tells you what belongs to the left vs right subtree.

Why do we need two traversals?

A single traversal is not enough to uniquely determine a binary tree. Consider:

Preorder: [1, 2]

Could be either:
    1       1
   /    or    \
  2            2

Both trees have the same preorder. We need a second traversal to disambiguate.

What each traversal tells us

• Preorder [root, ...left..., ...right...]: The first element is always the root
• Postorder [...left..., ...right..., root]: The last element is always the root
• Inorder [...left..., root, ...right...]: Everything left of the root belongs to the left subtree, everything right belongs to the right subtree

The inorder traversal is special — it tells us the boundary between left and right subtrees. This is why most constructions require inorder as one of the two inputs.

Construction from inorder + preorder

This is the most common variant (LeetCode 105).

Algorithm

1. The first element of preorder is the root
2. Find this root in the inorder array — everything to its left is the left subtree, everything to its right is the right subtree
3. The size of the left subtree tells us how to split the preorder array
4. Recurse on both halves

Step-by-step example

Preorder: [3, 9, 20, 15, 7]
Inorder:  [9, 3, 15, 20, 7]

Step 1: Root = preorder[0] = 3
Step 2: Find 3 in inorder → index 1
        Left inorder:  [9]        (1 element)
        Right inorder: [15, 20, 7] (3 elements)

Step 3: Split preorder (skip root):
        Left preorder:  [9]        (1 element — matches left inorder size)
        Right preorder: [20, 15, 7] (3 elements)

Step 4: Recurse
        Left subtree:  preorder=[9], inorder=[9] → leaf node 9
        Right subtree: preorder=[20,15,7], inorder=[15,20,7]
            Root = 20, left=[15], right=[7]
            → node 20 with children 15 and 7

Result:
    3
   / \
  9  20
    /  \
   15   7

Naive implementation (O(n^2))

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_pre_in(preorder, inorder):
    """Build tree from preorder and inorder traversals."""
    if not preorder or not inorder:
        return None

    # Root is first element of preorder
    root_val = preorder[0]
    root = TreeNode(root_val)

    # Find root in inorder to split left/right
    mid = inorder.index(root_val)

    # Left subtree: first 'mid' elements after root in preorder
    root.left = build_tree_pre_in(
        preorder[1:mid+1],
        inorder[:mid]
    )

    # Right subtree: remaining elements
    root.right = build_tree_pre_in(
        preorder[mid+1:],
        inorder[mid+1:]
    )

    return root

This works but is O(n^2) because inorder.index() is O(n) and array slicing creates copies.

Optimized implementation (O(n))

Use a hashmap for O(1) root lookups and indices instead of slicing:

def build_tree_optimized(preorder, inorder):
    """Build tree in O(n) using hashmap and index tracking."""
    # Map value → index in inorder for O(1) lookup
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    pre_idx = [0]  # use list to allow mutation in nested function

    def build(in_left, in_right):
        if in_left > in_right:
            return None

        # Pick the current root from preorder
        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)

        # Find root position in inorder
        mid = inorder_map[root_val]

        # Build left subtree first (preorder: root → left → right)
        root.left = build(in_left, mid - 1)
        root.right = build(mid + 1, in_right)

        return root

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

Key insight: We use a global preorder index (pre_idx[0]) that advances by 1 each time we create a node. Since preorder visits root, then left, then right, the index naturally follows the construction order.

Time: O(n). Space: O(n) for the hashmap + O(h) for recursion.

Construction from inorder + postorder

Very similar, but the root is the last element of postorder instead of the first (LeetCode 106).

Algorithm

1. Last element of postorder is the root
2. Find root in inorder to split left/right
3. Process right subtree first, then left (reverse of postorder’s build order)

def build_tree_post_in(inorder, postorder):
    """Build tree from inorder and postorder traversals."""
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    post_idx = [len(postorder) - 1]

    def build(in_left, in_right):
        if in_left > in_right:
            return None

        root_val = postorder[post_idx[0]]
        post_idx[0] -= 1
        root = TreeNode(root_val)

        mid = inorder_map[root_val]

        # Build RIGHT subtree first! (postorder: left → right → root)
        # We're going backwards, so right comes before left
        root.right = build(mid + 1, in_right)
        root.left = build(in_left, mid - 1)

        return root

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

Why right before left?

Postorder is [...left..., ...right..., root]. When we read from the end, we get root, ...right..., ...left.... So after the root, the next elements belong to the right subtree.

Example

Inorder:   [9, 3, 15, 20, 7]
Postorder: [9, 15, 7, 20, 3]

Step 1: Root = postorder[-1] = 3
        Find 3 in inorder → index 1
        Left inorder: [9], Right inorder: [15, 20, 7]

Step 2: Build right subtree next (post_idx moves to 20)
        Root = 20, find in inorder → index 3
        Right of 20: [7] → leaf 7
        Left of 20: [15] → leaf 15

Step 3: Build left subtree (post_idx moves to 9)
        Root = 9 → leaf node

Result:
    3
   / \
  9  20
    /  \
   15   7

Construction from preorder + postorder (full binary tree only)

Without inorder, we cannot always uniquely determine the tree. However, if the tree is full (every node has 0 or 2 children), preorder + postorder is sufficient (LeetCode 889).

Why inorder is usually needed

Consider preorder [1, 2] and postorder [2, 1]:

Could be:     1       or      1
             /                  \
            2                    2

Without inorder, we cannot tell if 2 is a left or right child. For a full binary tree, this ambiguity does not exist because every non-leaf has exactly 2 children.

Algorithm for full binary tree

1. First element of preorder is root
2. Second element of preorder is the root of the left subtree
3. Find this left root in postorder — everything before it (inclusive) is the left subtree
4. Recurse

def build_tree_pre_post(preorder, postorder):
    """Build full binary tree from preorder and postorder."""
    post_map = {val: idx for idx, val in enumerate(postorder)}
    pre_idx = [0]

    def build(post_left, post_right):
        if post_left > post_right:
            return None

        root_val = preorder[pre_idx[0]]
        pre_idx[0] += 1
        root = TreeNode(root_val)

        # If this is a leaf (only one element in range)
        if post_left == post_right:
            return root

        # Next in preorder is root of left subtree
        left_root_val = preorder[pre_idx[0]]
        left_root_post_idx = post_map[left_root_val]

        # Left subtree: post_left to left_root_post_idx
        root.left = build(post_left, left_root_post_idx)
        # Right subtree: left_root_post_idx+1 to post_right-1
        root.right = build(left_root_post_idx + 1, post_right - 1)

        return root

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

Example

Preorder:  [1, 2, 4, 5, 3, 6, 7]
Postorder: [4, 5, 2, 6, 7, 3, 1]

Root = 1 (preorder[0])
Left root = 2 (preorder[1])
Find 2 in postorder → index 2
Left subtree: postorder[0:2] = [4, 5, 2]
Right subtree: postorder[3:5] = [6, 7, 3]

Left subtree: root=2, left root=4
  Find 4 in postorder → index 0
  Left: [4] → leaf
  Right: [5] → leaf

Right subtree: root=3, left root=6
  Find 6 in postorder → index 3
  Left: [6] → leaf
  Right: [7] → leaf

Result:
      1
     / \
    2   3
   / \ / \
  4  5 6  7

Edge cases

Duplicate values

The hashmap approach assumes unique values. If values can repeat, you need a different strategy (track indices more carefully or use a multimap).

Empty arrays

# Always check for empty input
if not preorder or not inorder:
    return None

Single node

# preorder = [5], inorder = [5]
# Returns TreeNode(5) with no children

Mismatched arrays

If the arrays do not represent valid traversals of the same tree, the hashmap lookup will fail or produce garbage. In production, validate inputs.

Verification helper

After building a tree, verify it produces the expected traversals:

def get_preorder(root):
    if not root:
        return []
    return [root.val] + get_preorder(root.left) + get_preorder(root.right)

def get_inorder(root):
    if not root:
        return []
    return get_inorder(root.left) + [root.val] + get_inorder(root.right)

def get_postorder(root):
    if not root:
        return []
    return get_postorder(root.left) + get_postorder(root.right) + [root.val]

# Test
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]

root = build_tree_optimized(preorder, inorder)

assert get_preorder(root) == preorder
assert get_inorder(root) == inorder
print("Tree constructed correctly!")

Summary of combinations

Combination	Unique tree?	Notes
Inorder + Preorder	Yes	Most common
Inorder + Postorder	Yes	Similar approach
Preorder + Postorder	Only for full trees	Ambiguous for general trees
Preorder only	No	Cannot distinguish left vs right
Inorder only	No	Cannot determine root
Postorder only	No	Cannot determine root position

The rule: You need inorder to split left and right subtrees. The other traversal identifies the root.

Constructing BST from preorder alone

BSTs are special — the BST property provides the split information that inorder normally gives. Given a preorder traversal of a BST, you can reconstruct it:

def bst_from_preorder(preorder):
    """Build BST from preorder traversal alone (LeetCode 1008)."""
    idx = [0]

    def build(min_val, max_val):
        if idx[0] >= len(preorder):
            return None

        val = preorder[idx[0]]
        if val < min_val or val > max_val:
            return None

        idx[0] += 1
        node = TreeNode(val)
        node.left = build(min_val, val)
        node.right = build(val, max_val)
        return node

    return build(float('-inf'), float('inf'))

This works because in a BST, we know that left subtree values are < root and right subtree values are > root — the same information that inorder gives us.

Practice problems

1. Construct Binary Tree from Preorder and Inorder (LeetCode 105) — The classic
2. Construct Binary Tree from Inorder and Postorder (LeetCode 106) — Mirror approach
3. Construct Binary Tree from Preorder and Postorder (LeetCode 889) — Full binary tree
4. Construct BST from Preorder (LeetCode 1008) — BST property as split info
5. Verify Preorder Serialization (LeetCode 331) — Related validation problem
6. Serialize and Deserialize Binary Tree (LeetCode 297) — Uses similar ideas

Key takeaways

• Preorder/postorder identify the root; inorder identifies the left/right split
• Use a hashmap for O(1) root lookups — converts O(n^2) to O(n)
• Track a global index into preorder/postorder instead of slicing arrays
• For preorder: process left before right; for postorder: process right before left
• BSTs are special — preorder alone is sufficient because the BST property provides the split
• Always verify by checking if the constructed tree produces the original traversals