LeetCode 105 · Trees

Construct Binary Tree from Preorder and Inorder Traversal, explained with a picture

Rebuilding a family tree from two lists.

MediumTrees
▶ Watch it step by step

The problem

You are given two lists of a tree’s values: its preorder (node, left, right) and inorder (left, node, right) traversals. Rebuild the tree.

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

Picture it

Picture rebuilding a family tree from two lists. The first name in preorder is always the root (the eldest). Find that name in the inorder list: everyone to its left belongs to the left family, everyone to its right to the right family. Repeat the same trick on each side.

How to recognise it

  • You are given two traversals of the same tree and must rebuild the tree.
  • Preorder (node, left, right) always starts with the root of whatever part you are looking at.
  • Inorder (left, node, right) has the root in the middle: everything before it is the left subtree, everything after it the right subtree.
  • One list tells you which node is the root, the other tells you how to split. That is divide and conquer: solve the left part and the right part the same way.
  • Up to 3,000 nodes with unique values, so a value identifies a node.

Start with brute force

Take the root from the front of preorder, find it in inorder with a linear search, slice both lists into left and right parts, and recurse.

def build_brute(preorder, inorder):
    if not preorder:
        return None
    root = Node(preorder[0])
    mid = inorder.index(root.val)              # linear search
    root.left = build_brute(preorder[1:mid + 1], inorder[:mid])
    root.right = build_brute(preorder[mid + 1:], inorder[mid + 1:])
    return root

It is correct: the left subtree has mid nodes, so it takes the next mid values of preorder. But every call searches and copies lists in O(n), so a lopsided tree costs O(n²): about 10^7 steps for a 3,000-node chain. That still passes here, but the work is wasted.

From brute force to the idea

  1. Find the waste. inorder.index searches the same list again and again, and the slices copy values that never change.
  2. Look positions up in O(1). Build where, a dictionary from value to its position in inorder, once. Then mid = where[root.val] is instant.
  3. Use bounds instead of slices. make(lo, hi) builds the subtree whose values are inorder[lo..hi]. The left part is lo..mid - 1, the right part mid + 1..hi, and an empty range (lo > hi) means no node.
  4. Read preorder as a stream. Preorder lists the root, then the whole left subtree, then the whole right one. If make builds the left subtree before the right, the roots are needed in exactly preorder order, so next(nxt) on one shared iterator always yields the right root.

This is the key idea: preorder supplies the roots in order, and the inorder position of each root splits the remaining range in O(1).

The page leaves out the Node class; it is the usual one with val, left and right.

The key idea

Preorder gives the root; its position in inorder splits left and right subtrees. With a value→index map: O(n).

Python solution

def build(preorder, inorder):
    where = {v: i for i, v in enumerate(inorder)}
    nxt = iter(preorder)               # preorder gives roots in order
    def make(lo, hi):                  # inorder[lo..hi]
        if lo > hi:
            return None
        root = Node(next(nxt))
        mid = where[root.val]           # splits left and right
        root.left = make(lo, mid - 1)
        root.right = make(mid + 1, hi)
        return root
    return make(0, len(inorder) - 1)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (search and slice)O(n²) worst case: O(n) search and copies per node; about O(n log n) if balancedO(n²) worst case for the slices alive along a deep path
Dictionary + bounds (shown code)O(n): one dictionary build, then O(1) work per nodeO(n): the dictionary, plus O(h) recursion stack

Edge cases

  • Single node: [1], [1] gives a single node.
  • Empty lists: make(0, -1) returns None at once.
  • Chains ([3, 2, 1] and [1, 2, 3]): a left-leaning chain; one side of every range is empty.
  • Duplicate values: the method breaks, because where keeps only one position per value. For [1, 1, 1] and [1, 1, 1] the shown code runs out of preorder values and raises StopIteration. LeetCode promises unique values.
  • Very deep tree: a chain of about 1,000 nodes exceeds Python's default recursion limit, and LeetCode allows 3,000 nodes; raise the limit or rebuild iteratively.

Common mistakes

  • Building the right subtree before the left while still reading preorder from the front: the stream then hands out the wrong roots.
  • Off-by-one errors in the slices or bounds, such as using mid instead of mid - 1.
  • Searching inorder with .index inside the recursion, which brings back O(n²).
  • Assuming the values are sorted and splitting by comparison: the tree is not a BST.
Your turn: inorder and postorder

Rebuild the tree from its inorder and postorder (left, right, node) traversals (LeetCode 106). For inorder [9, 3, 15, 20, 7] and postorder [9, 15, 7, 20, 3] the answer is [3, 9, 20, null, null, 15, 7]. Describe your approach, then write it if you like.

Compare with our answer

Postorder ends with the root. Read it from the back: that gives the root, then the whole right subtree, then the left one. So build the right subtree first.

def build_post(inorder, postorder):
    where = {v: i for i, v in enumerate(inorder)}
    nxt = iter(reversed(postorder))          # roots, last first
    def make(lo, hi):
        if lo > hi:
            return None
        root = Node(next(nxt))
        mid = where[root.val]
        root.right = make(mid + 1, hi)       # right subtree comes first
        root.left = make(lo, mid - 1)
        return root
    return make(0, len(inorder) - 1)

Time O(n), space O(n).

A strong answer mentions: reading postorder backwards, switching the build order to right before left, and keeping the dictionary of inorder positions.

Check what stuck

1. You must rebuild a tree from its level order list and its inorder list, with unique values. Which idea from this problem carries over?

2. Why can the shown code read preorder with a single shared iterator?

3. A learner builds root.right before root.left in the shown code. Which input is still rebuilt correctly?

Score 60% or more and the lesson is marked complete.