Construct Binary Tree from Preorder and Inorder Traversal

Table of Contents +

A tree looks like a drawing on paper. But a computer cannot store a drawing. It can only store lists of numbers. So how do you turn two flat lists back into the real tree shape? That is what this question tests. It looks scary at first. Once you see one small trick, it becomes easy.

🎯 The Problem

You get two flat lists and must rebuild the exact tree they came from.

The rules:

  • The preorder list visits the root first, then the whole left side, then the whole right side.
  • The inorder list visits the whole left side first, then the root, then the whole right side.
  • Every value in the tree is different. So you can find any value in the lists without confusion.
  • Return the rebuilt tree.

Let us use a small example. The preorder list is [3, 9, 20, 15, 7]. The inorder list is [9, 3, 15, 20, 7]. The tree that produced both of these looks like this.

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


Output (the tree):
        3
       / \
      9  20
         /  \
        15   7


Explanation: 3 is the root. In inorder, 9 sits left of 3, so 9 is the left subtree.
20, 15, 7 sit right of 3, so they form the right subtree.

Here is the tree drawn out, so you can keep it in your head while we work.

3

9

20

15

7

🐢 Approach 1: Slice and Search Every Time (Brute Force)

The idea in one line: the front of preorder is the root, find it in inorder, then split into left and right and repeat.

The idea:

  • The first value in preorder is always the root. Preorder visits the root before anything else.
  • So 3 is the root of the whole tree.
  • In inorder, everything left of the root is the left subtree. Everything right of it is the right subtree.

How it works:

  • Take the front of preorder as the root.
  • Search the whole inorder list to find that root.
  • Split inorder at that point into a left slice and a right slice.
  • Cut new smaller lists and call the same function again on each.

Why it is weak:

  • Each call searches the whole inorder list to find the root.
  • Each call copies parts of the lists into new smaller lists.
  • On a one-sided tree this climbs to O(n²) time and wastes memory on copies.

Here is the slice-and-search code:

build_tree_slice_search.py
def build_tree(preorder, inorder):
    if not preorder: return None
    root = TreeNode(preorder[0])
    mid = inorder.index(root.val)
    root.left = build_tree(preorder[1:1 + mid], inorder[:mid])
    root.right = build_tree(preorder[1 + mid:], inorder[mid + 1:])
    return root

⚡ Approach 2: Hash Map Plus a Moving Pointer (Best)

The idea in one line: replace the search with an instant lookup, and replace the slicing with plain index numbers.

The idea:

  • A hash map stores a key and value and looks the key up almost instantly.
  • Build one map from each inorder value to its position. Then finding the root is one lookup, not a scan.
  • Keep one moving pointer into preorder that always points at the next root to place.

How it works:

  • Take the value at the preorder pointer as the root. Move the pointer forward.
  • Look up the root’s position in inorder using the map.
  • That position splits the current inorder slice into a left part and a right part.
  • Build the left subtree first, then the right, passing left and right boundaries instead of copying.

Why it is fast:

  • No repeated searching. The map answers in one step.
  • No copying. We pass index boundaries, just numbers.
  • Each node is touched once, so the work drops to O(n).

Here is a picture of how the root from preorder splits the inorder list into two sides.

preorder: 3 is the next root

find 3 in inorder

left of 3: [9] becomes left subtree

right of 3: [15,20,7] becomes right subtree

next preorder value 9 builds left

next preorder value 20 builds right

Steps to Solve

  1. Build a hash map from each inorder value to its index. Do this once.
  2. Keep a pointer that starts at the front of the preorder list. It marks the next root to place.
  3. Write a helper that builds the subtree for an inorder slice between a left and a right boundary.
  4. If the left boundary passes the right boundary, the slice is empty. Return nothing.
  5. Take the value at the preorder pointer as the root. Move the pointer forward by one.
  6. Use the map to find that root’s position inside inorder.
  7. Build the left subtree from the slice left of that position. Then build the right subtree from the slice right of it.
  8. Attach both subtrees to the root and return the root.

This Python version uses a dictionary for the inorder lookup and a list as a queue to print the tree level by level.

construct_tree.py
from collections import deque




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




def build_tree(preorder, inorder):
    pos = {val: i for i, val in enumerate(inorder)}  # value -> inorder index
    pre_idx = 0  # next root to place


    def build(in_left, in_right):
        nonlocal pre_idx
        if in_left > in_right:           # empty slice
            return None
        root_val = preorder[pre_idx]     # next root from preorder
        pre_idx += 1                     # move the pointer forward
        root = Node(root_val)
        mid = pos[root_val]              # root's place in inorder
        root.left = build(in_left, mid - 1)    # left slice first
        root.right = build(mid + 1, in_right)  # then right slice
        return root


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




def print_levels(root):
    queue = deque([root])
    while queue:
        count = len(queue)
        row = []
        for _ in range(count):
            cur = queue.popleft()
            row.append(str(cur.val))
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
        print(" ".join(row))




preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
tree = build_tree(preorder, inorder)
print_levels(tree)

The output of the above code will be:

3
9 20
15 7

Let us walk through the Python version line by line, so the trick is fully clear.

The line pos = {val: i for i, val in enumerate(inorder)} builds the lookup map once. The key is a value from inorder. The value is the index where it sits. We do this so that finding the root later is one instant step, not a scan.

The line pre_idx = 0 is our moving pointer into preorder. It always points at the next root we must place. We keep it outside the inner function so every call shares the same pointer.

Inside build, the line if in_left > in_right: return None is the stop condition. When the slice has no values left, the subtree is empty. So we return nothing.

The line root_val = preorder[pre_idx] grabs the next root. Remember, preorder always gives the root first. Then pre_idx += 1 moves the pointer so the next call gets the next root. The order matters. We move it forward right after using it.

The line mid = pos[root_val] is the heart of the solution. It finds where this root sits inside inorder. That position is the split point. Everything before mid is the left subtree. Everything after mid is the right subtree.

The line root.left = build(in_left, mid - 1) builds the left side first. This is on purpose. Preorder fills the left subtree completely before the right one. So we must consume the left preorder values first. Only after that does root.right = build(mid + 1, in_right) build the right side.

⏱️ Time and Space Complexity

The slow way scans inorder on every call and copies slices, so it climbs to O(n²) and uses extra memory for the copies. The optimal way replaces the scan with a one-time map and replaces copying with plain index numbers. So each node is touched once. That gives O(n) time. The space is O(n) for the map plus the recursion depth.

Approach Time Complexity Space Complexity
Slice and search each call O(n²) O(n²)
Hash map plus moving pointer O(n) O(n)

Tip

The one idea to remember: preorder hands you the root, and inorder tells you how to split the rest into left and right. Say that sentence out loud in the interview before you write any code.

🧩 Key Takeaways

  • ✅ The first value in preorder is always the root of the current subtree.
  • ✅ Finding that root inside inorder splits the rest into a left part and a right part.
  • ✅ A hash map from value to inorder index turns the search into one instant lookup.
  • ✅ A moving preorder pointer plus left and right boundaries removes all list copying.
  • ✅ Build the left subtree before the right, because preorder fills the left side first.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In a preorder traversal, which node comes first?

    Why: Preorder visits the root first, then the left subtree, then the right subtree. So the first value is always the root.

  2. 2

    Once you know the root, what does the inorder list tell you?

    Why: In inorder, values left of the root belong to the left subtree and values right of it belong to the right subtree.

  3. 3

    Why do we build a hash map from inorder values to their indices?

    Why: The map turns the repeated search for the root inside inorder into a single instant lookup, which removes the O(n²) cost.

  4. 4

    What is the time complexity of the optimal approach?

    Why: With the map for lookups and index boundaries instead of copies, each node is processed once, giving O(n) time.

Score: 0 / 4

🚀 What’s Next?

Previous Kth Smallest Element in a BST Next Binary Tree Maximum Path Sum