Build A Binary Tree From Preorder And Inorder Traversals

To build a binary tree from preorder and inorder traversals, you use the predictable order in which nodes are visited by each traversal. Think about it: preorder visits the root before its subtrees, while inorder visits the left subtree, then the root, then the right subtree. By combining these two sequences, you can reconstruct the original binary tree when all node values are unique.

Worth pausing on this one.

Introduction to Building a Binary Tree from Traversals

A binary tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. Traversals are methods for visiting every node in a tree in a specific order. The two most important traversals for reconstructing a binary tree are:

• Preorder traversal: root → left subtree → right subtree
• Inorder traversal: left subtree → root → right subtree

Given both preorder and inorder traversal arrays, it is possible to recreate the original binary tree, assuming that every value in the tree is unique. This is a common programming problem because it tests your understanding of recursion, tree traversal, and array indexing.

Take this: suppose the preorder traversal is:

[3, 9, 20, 15, 7]

and the inorder traversal is:

[9, 3, 15, 20, 7]

The first value in preorder is 3, so 3 must be the root of the tree. On the flip side, in inorder traversal, values to the left of 3 belong to the left subtree, and values to the right of 3 belong to the right subtree. This allows us to divide the problem into smaller recursive subproblems Which is the point..

Understanding the Key Idea

The most important observation is:

The first element in preorder traversal is always the root of the current subtree.

Once we know the root value, we can search for that value in the inorder traversal. The position of the root in inorder tells us how many nodes belong to the left subtree and how many nodes belong to the right subtree And that's really what it comes down to. But it adds up..

The official docs gloss over this. That's a mistake.

For example:

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

The first element in preorder is 3, so 3 is the root.

In inorder:

[9, 3, 15, 20, 7]
     ^

The value 3 is at index 1 That's the part that actually makes a difference..

That means:

• 9 is in the left subtree
• 15, 20, 7 are in the right subtree

So the tree starts like this:

      3
     / \
    9   ?
       / \
      ?   ?

Now we recursively build the left and right subtrees And that's really what it comes down to..

Step-by-Step Algorithm

To build a binary tree from preorder and inorder traversals, follow these steps:

1. Check the base case

   • If either traversal is empty, return None.

2. Find the root

   • The first element in preorder is the root of the current subtree.

3. Find the root in inorder

   • Locate the root value in the inorder array.
   • This index separates the left subtree from the right subtree.

4. Count left subtree nodes

   • The number of elements before the root in inorder is the size of the left subtree.

5. Build the left subtree

   • Use the next portion of preorder and the left portion of inorder.

6. Build the right subtree

   • Use the remaining portion of preorder and the right portion of inorder.

7. Return the root

   • Attach the built left and right subtrees to the root and return it.

Example Walkthrough

Consider:

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

Step 1: Build the root

The first value in preorder is 3 Simple as that..

root = 3

Step 2: Find 3 in inorder

inorder = [9, 3, 15, 20, 7]
              ^

The index of 3 is 1.

This means there is 1 node in the left subtree and 3 nodes in the right subtree.

Step 3: Divide the arrays

Left subtree:

preorder  = [9]
inorder   = [9]

Right subtree:

preorder  = [20, 15, 7]
inorder   = [15, 20, 7]

Step 4: Recursively build subtrees

For the right subtree:

preorder  = [20, 15, 7]
inorder   = [15, 20, 7]

The first value is 20, so 20 is the root of the right subtree Nothing fancy..

In inorder:

[15, 20, 7]
     ^

So:

• 15 is the left child of 20
• 7 is the right child of 20

The final tree is:

      3
     / \
    9   20
       /  \
      15   7

Python Implementation

Here is a clean Python solution using an index map for efficient lookup:

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

def buildTree(preorder, inorder):
    inorder_index = {value: index for index, value in enumerate(inorder)}
    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index

        if left > right:
            return None

        root_value = preorder[preorder_index]
        preorder_index += 1

        root = TreeNode(root_value)

        inorder_position = inorder_index[root_value]

        root.left = build(left, inorder_position - 1)
        root.right = build(inorder_position + 1, right)

return root

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

How the Code Works

The implementation relies on a closure variable preorder_index that advances globally as each node is created. Since preorder traversal visits nodes in the order root → left → right, we simply consume elements from left to right, and the recursive calls naturally handle the correct subtree boundaries.

The inorder_index dictionary eliminates the need to search for the root position in every recursive call, turning what would be a linear scan into a constant-time lookup The details matter here..

Key Details

• left > right is the stopping condition. When the boundary collapses, there are no more nodes to place, so we return None.
• preorder_index increments before building children, ensuring the next value is consumed at the right moment.
• The order of recursion matters. We must build the left subtree first because preorder processes the left subtree immediately after the root. If we built the right subtree first, preorder_index would advance into the wrong portion of the array.

Complexity Analysis

Summary

Reconstructing a binary tree from preorder and inorder traversals is a classic divide-and-conquer problem. In practice, the preorder sequence always identifies the current root, while the inorder sequence reveals how the remaining nodes split between the left and right subtrees. By pairing these two properties and using a hash map for fast index lookups, we can build the entire tree efficiently in a single pass. This pattern also generalizes to related problems, such as constructing a tree from inorder and postorder traversals, where the root is instead taken from the end of the postorder array and the recursion order is reversed.