Build a tree from preorder and inorder in Python

Why this lesson matters

Some problems give you two lists that were made by walking the same tree in two different orders, and ask you to find the tree again. A walk turns a tree into a plain list. Two lists from two walks can, together, be turned back into one tree. This is a common interview question, and it shows how the order of the walk carries information about the shape.

The previous lesson saved a tree as text with null markers, and rebuilt it from that text in one pass. This lesson uses a different input. There are no markers. The two lists must do the job of the markers, and the method must find where the left side ends and the right side begins.

By the end of this lesson you will rebuild a tree from preorder and inorder lists, explain why one list alone is not enough, and write the build with a dictionary from value to position. You will count the work done, and test the method on random trees. You will also see the mistakes that give an error or a wrong tree. The next lesson in this module builds a tree from inorder and postorder lists, where the root is taken from the end of the postorder list instead of the start of the preorder list.

The two walks

Here are the two walks that the lesson uses. Both visit every node once. They differ in when the node itself is visited.

Preorder visits the node first, then the left subtree, then the right subtree. The root is always the first item.

Inorder visits the left subtree first, then the node, then the right subtree. The root sits in the middle of the list, with the whole left subtree before it and the whole right subtree after it.

Take this tree:

Preorder gives 3, 9, 20, 15, 7. Inorder gives 9, 3, 15, 20, 7.

Look at the inorder list. The value 3 is at position 1. Everything before position 1 is in the left subtree: that is 9. Everything after it is in the right subtree: 15, 20, 7. So the inorder list tells you how many nodes sit on each side of the root.

Look at the preorder list. The first item is 3, which is the root. The items after the root are the left subtree first, then the right subtree. The left subtree has one node, so its block is 9. The right subtree takes what is left, 20, 15, 7.

Put the two facts together and you have the rule for the whole method. The first item of the preorder block is the root. Find the root in the inorder block. The inorder block before the root is the left subtree, and its size tells you how many items of the preorder block after the root belong to the left subtree. Each side is a smaller problem of the same kind.

Why one list is not enough

Preorder alone does not describe one tree. Look at these two trees, each with two nodes:

tree A: 1 with a left child 2
tree B: 1 with a right child 2

Both have the preorder list 1, 2. Their inorder lists are different, though. Tree A gives inorder 2, 1, because the left child comes before the root. Tree B gives inorder 1, 2, because the root comes before the right child. The second list is what tells the two trees apart.

Inorder alone does not describe one tree either. The inorder list 1, 2 fits tree B, and it also fits tree C, where 2 is the root and 1 is its left child. Preorder tells you which value is the root, and inorder tells you where the root splits the rest. You need both.

The idea, step by step

Use the example tree from above, with preorder 3, 9, 20, 15, 7 and inorder 9, 3, 15, 20, 7.

The first preorder item is 3. Make the root 3.
Find 3 in the inorder list. It is at index 1, counting from 0.
Left side: the inorder items before index 1 are 9. That is one node, so the left subtree has size 1. Its preorder block is the next one item: 9.
Right side: the inorder items after index 1 are 15, 20, 7. That is three nodes. Its preorder block is the rest of the preorder list: 20, 15, 7.
Build the left subtree from preorder 9 and inorder 9. It is one node. Its root is 9.
Build the right subtree from preorder 20, 15, 7 and inorder 15, 20, 7. The first preorder item is 20, the root. In inorder, 20 is at index 1 of this block. The left side is 15, and the right side is 7.

The method only ever looks at a block of each list. A block is a range of positions, with a start and an end. Each call gets two ranges, one in preorder and one in inorder, and it builds one subtree from them.

The ranges

Each call needs three numbers. The first is where its preorder block starts. The second and third are where its inorder block starts and ends. The size of the preorder block always equals the size of the inorder block, so the end of the preorder block does not need its own number.

For a call with preorder start p, and inorder range from s to e:

The root is preorder[p].
Let m be the inorder position of the root.
The left subtree has m - s nodes. Its preorder block starts at p + 1, and its inorder block is from s to m - 1.
The right subtree starts in preorder right after the left block, at p + 1 + (m - s). Its inorder block is from m + 1 to e.

The number m - s is the size of the left subtree, and it tells you how far to skip in preorder. This is the main idea, and the code below uses exactly these two lines.

A call with an empty inorder range (s greater than e) is an empty tree. It returns None, the same as the base case in the previous lesson.

Finding the root quickly

Each call needs the inorder position of its root. The simple way is to scan the inorder block until you find the value. That scan takes time proportional to the block size. In a chain of 1,000 nodes, where each root is at the end of its block, the scans add up to about half a million comparisons. Example 3 below counts them exactly.

The fix is a dictionary from value to inorder position. Build it once, before the recursion starts, by walking the inorder list once. The dictionary comprehension {v: i for i, v in enumerate(inorder)} does this in one line, and enumerate gives each value with its position. After that, each lookup is a single step on average. A Python dictionary gives this behaviour: a lookup takes about the same time no matter how many entries it holds. The dictionary costs extra memory, one entry for each node.

With the dictionary, the whole build takes O(n) time. Here O(n) means the work grows in step with the number of nodes n: double the nodes, and the work roughly doubles. The function does constant work at each node and one dictionary lookup, so there are about n lookups in all. The dictionary and the recursion each take O(n) memory.

The code

The program below builds the tree from the example, prints the tree in a compact shape, walks it again to check the lists, and then rebuilds 2,000 random trees. The random trees come from random.Random(42), a generator with a fixed seed, so the same numbers come out on every run.

Python · editable

import itertools
import random

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

def build_tree(preorder, inorder):
    index_of = {v: i for i, v in enumerate(inorder)}
    return build(preorder, 0, 0, len(inorder) - 1, index_of)

def build(preorder, pre_start, in_start, in_end, index_of):
    if in_start > in_end:
        return None
    root_val = preorder[pre_start]
    node = TreeNode(root_val)
    mid = index_of[root_val]
    left_size = mid - in_start
    node.left = build(preorder, pre_start + 1, in_start, mid - 1, index_of)
    node.right = build(preorder, pre_start + 1 + left_size, mid + 1, in_end, index_of)
    return node

def preorder_of(node, out):
    if node is None:
        return
    out.append(node.val)
    preorder_of(node.left, out)
    preorder_of(node.right, out)

def inorder_of(node, out):
    if node is None:
        return
    inorder_of(node.left, out)
    out.append(node.val)
    inorder_of(node.right, out)

def shape(node):
    if node is None:
        return "null"
    return f"{node.val}({shape(node.left)},{shape(node.right)})"

def random_tree(rng, size, counter):
    if size == 0:
        return None
    left_size = rng.randrange(size)
    node = TreeNode(next(counter))
    node.left = random_tree(rng, left_size, counter)
    node.right = random_tree(rng, size - 1 - left_size, counter)
    return node

print("example 1 shape:", shape(build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])))

pre = []
inord = []
example1 = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
preorder_of(example1, pre)
inorder_of(example1, inord)
print("example 1 preorder again:", pre)
print("example 1 inorder again:", inord)

print("example 2 shape:", shape(build_tree([1, 2, 3], [3, 2, 1])))
print("example 3 single node:", shape(build_tree([-4], [-4])))
print("example 4 shape:", shape(build_tree([10, 5, 2, 1, 7, 15, 12, 20],
                                           [1, 2, 5, 7, 10, 12, 15, 20])))

rng = random.Random(42)
trials = 2000
passed = 0
for _ in range(trials):
    size = rng.randrange(12)
    original = random_tree(rng, size, itertools.count(1))
    p = []
    q = []
    preorder_of(original, p)
    inorder_of(original, q)
    rebuilt = build_tree(p, q)
    if shape(rebuilt) == shape(original):
        passed += 1
print(f"random trees rebuilt exactly: {passed} of {trials}")

Output:

example 1 shape: 3(9(null,null),20(15(null,null),7(null,null)))
example 1 preorder again: [3, 9, 20, 15, 7]
example 1 inorder again: [9, 3, 15, 20, 7]
example 2 shape: 1(2(3(null,null),null),null)
example 3 single node: -4(null,null)
example 4 shape: 10(5(2(1(null,null),null),7(null,null)),15(12(null,null),20(null,null)))
random trees rebuilt exactly: 2000 of 2000

The shape string writes each node as its value, then its left and right children in brackets. A null inside the brackets is an empty child. The string makes the shape easy to compare by eye.

The check in the last part is worth copying into your own tests. Build a random tree, walk it into two lists, rebuild from the lists, and compare the shapes. A function that passes on 2,000 random trees of up to 11 nodes is very likely right. Random trees with distinct values are used here on purpose: the common mistakes section explains what goes wrong when values repeat.

The itertools.count(1) call makes an endless counter. Each call to next(counter) returns the next number, so each new node gets a value that no other node has.

Example 2: a chain

The second example is a chain that leans left. Its preorder is 1, 2, 3 and its inorder is 3, 2, 1. The root is 1, and it is at the end of the inorder list. So the whole rest of the inorder list is the left subtree, and the right subtree is empty.

preorder: 1, 2, 3
inorder:  3, 2, 1

Step by step: the root 1 is at inorder index 2. The left side has 2 - 0 = 2 nodes, so the left block is inorder 3, 2 and preorder 2, 3. The right side has 2 - 2 = 0 nodes, so the right range is empty and returns None. In the next call, the root is 2, found at inorder index 1 of its block. Its left side has 1 node, 3, and its right side is empty. The result is 1(2(3(null,null),null),null), the same as the output above.

Example 3: a counted search versus a dictionary

The third example measures why the dictionary matters. The program below builds a chain twice. The first build finds each root by scanning the inorder list. The second build looks the root up in a dictionary. The program counts the work of each.

The chain here has 900 nodes, not 1,000. Python's default recursion limit is 1000, and each build call goes one level deeper for each node in the chain, so 1,000 nodes would need more calls than the limit allows. A chain of 1,000 nodes makes this code raise RecursionError.

Python · editable

comparisons = 0
lookups = 0

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

def build_with_search(preorder, pre_start, in_start, in_end, inorder):
    global comparisons
    if in_start > in_end:
        return None
    root_val = preorder[pre_start]
    mid = in_start
    while inorder[mid] != root_val:
        comparisons += 1
        mid += 1
    comparisons += 1
    node = TreeNode(root_val)
    left_size = mid - in_start
    node.left = build_with_search(preorder, pre_start + 1, in_start, mid - 1, inorder)
    node.right = build_with_search(preorder, pre_start + 1 + left_size, mid + 1, in_end, inorder)
    return node

def build_with_map(preorder, pre_start, in_start, in_end, index_of):
    global lookups
    if in_start > in_end:
        return None
    root_val = preorder[pre_start]
    node = TreeNode(root_val)
    lookups += 1
    mid = index_of[root_val]
    left_size = mid - in_start
    node.left = build_with_map(preorder, pre_start + 1, in_start, mid - 1, index_of)
    node.right = build_with_map(preorder, pre_start + 1 + left_size, mid + 1, in_end, index_of)
    return node

n = 900
preorder = [i + 1 for i in range(n)]
inorder = [0] * n
for i in range(n):
    inorder[n - 1 - i] = i + 1

build_with_search(preorder, 0, 0, n - 1, inorder)
print(f"search version, comparisons on a chain of {n}: {comparisons}")

index_of = {v: i for i, v in enumerate(inorder)}
build_with_map(preorder, 0, 0, n - 1, index_of)
print(f"map version, lookups on the same chain: {lookups}")

Output:

search version, comparisons on a chain of 900: 405450
map version, lookups on the same chain: 900

The search version does 405,450 comparisons. That number is 900 * 901 / 2. The chain has its roots at the far end of each block, so the first call scans 900 positions, the next scans 899, and so on down to 1. The map version does exactly one lookup per node. For 900 nodes that is 900 lookups, against 405,450 comparisons. The gap grows with the size of the tree: for 10,000 nodes the search version would do about 50 million comparisons, and the map version still does 10,000 lookups.

The global lines let the two functions add to the counters at the top of the program. Without them, comparisons += 1 would create a new variable inside the function, and the counter at the top would stay at zero.

Common mistakes

Passing the wrong start to the right side

The right subtree's preorder block starts after the left block, so its start is pre_start + 1 + left_size. A common slip is to write pre_start + left_size, which is one position too early. The right subtree then gets its root from the wrong place in preorder. The next example shows what Python does with that slip on the 7-node tree with preorder 1, 2, 4, 5, 3, 6, 7 and inorder 4, 2, 5, 1, 6, 3, 7. The code is shown without the run mark because it stops with an error.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build_wrong(preorder, pre_start, in_start, in_end, index_of):
    if in_start > in_end:
        return None
    root_val = preorder[pre_start]
    node = TreeNode(root_val)
    mid = index_of[root_val]
    left_size = mid - in_start
    node.left = build_wrong(preorder, pre_start + 1, in_start, mid - 1, index_of)
    node.right = build_wrong(preorder, pre_start + left_size, mid + 1, in_end, index_of)
    return node
 
 
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
index_of = {v: i for i, v in enumerate(inorder)}
build_wrong(preorder, 0, 0, len(inorder) - 1, index_of)

The output is:

Traceback (most recent call last):
  File "main.py", line 23, in <module>
    build_wrong(preorder, 0, 0, len(inorder) - 1, index_of)
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 15, in build_wrong
    node.left = build_wrong(preorder, pre_start + 1, in_start, mid - 1, index_of)
                ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 16, in build_wrong
    node.right = build_wrong(preorder, pre_start + left_size, mid + 1, in_end, index_of)
                 ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
  File "main.py", line 15, in build_wrong
    node.left = build_wrong(preorder, pre_start + 1, in_start, mid - 1, index_of)
                ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded

The lines between the first and the last call are left out here, because the traceback is about 3,000 lines long. The wrong start makes the right call read a position that belongs to an earlier root, so the calls keep nesting until Python stops them at its recursion limit. The number of frames depends on the Python version and on how much of the stack the program already used. The fix is the + 1. Each call must move past its own root, and then past the left block.

Duplicate values

The dictionary stores one position for each value. If a value appears twice, the second entry replaces the first, and the position is wrong for one of the copies. The two trees below have the same preorder list 1, 1 and the same inorder list 1, 1:

Python · editable

Output:

preorder [1, 1], inorder [1, 1]
preorder [1, 1], inorder [1, 1]

The two lists cannot say which copy is the left child and which is the right child. So the input does not have one answer, and the function has no way to choose correctly. The problem you are given will say that the values are distinct. If it does not, ask what the answer should be before you write code.

When the lists have duplicates and the function is run on them anyway, it can fail rather than return a tree. With preorder 1, 1 and inorder 1, 1, the dictionary keeps only the position 1 for the value 1, and the build reads past the end of the preorder list. The code is shown without the run mark because it stops with an error.

index_of = {v: i for i, v in enumerate([1, 1])}
preorder = [1, 1]
 
 
def build(pre_start, in_start, in_end):
    if in_start > in_end:
        return None
    root_val = preorder[pre_start]
    mid = index_of[root_val]
    left_size = mid - in_start
    build(pre_start + 1, in_start, mid - 1)
    build(pre_start + 1 + left_size, mid + 1, in_end)
 
 
build(0, 0, 1)

The output is:

Traceback (most recent call last):
  File "main.py", line 15, in <module>
    build(0, 0, 1)
    ~~~~~^^^^^^^^^
  File "main.py", line 11, in build
    build(pre_start + 1, in_start, mid - 1)
    ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 11, in build
    build(pre_start + 1, in_start, mid - 1)
    ~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 8, in build
    root_val = preorder[pre_start]
               ~~~~~~~~^^^^^^^^^^^
IndexError: list index out of range

The second copy of 1 sends the recursion past the end of the preorder list. The message says the index was out of range, which is the sign of a list that has run out of items.

Lists of different lengths

Each call reads a block from both lists. If the preorder list is shorter than the inorder list, the reads run past the end of the preorder list. Python then raises IndexError, with the message list index out of range. Check that both lists have the same length before building. The first line of build_tree is a good place for that check: if len(preorder) != len(inorder): raise ValueError(...).

A value that is not in inorder

If the preorder list has a value that the inorder list does not have, the dictionary lookup index_of[root_val] fails with a KeyError that names the missing value. The code is shown without the run mark because it stops with an error.

index_of = {1: 0, 2: 1}
index_of[9]

The output is:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    index_of[9]
    ~~~~~~~~^^^
KeyError: 9

The fix is to check the lookup and raise an error with a clear message. The exercises ask you to add that check.

Searching inorder with a loop

Some first attempts use a loop to find the root in inorder, as in the search version above. The answer is correct, but on a lopsided tree it does about half a million comparisons for 1,000 nodes, as the counts above show. Use the dictionary. Build it once, before the recursion starts, not inside each call, because building a dictionary inside each call costs the same as the scan you wanted to avoid.

Practice

Build the tree from preorder 1, 2, 4, 5, 3 and inorder 4, 2, 5, 1, 3. Write its shape string.

Show the answer

The root is 1, at inorder index 3. The left side is 4, 2, 5 (3 nodes), and the right side is 3. The left block of preorder is 2, 4, 5. Its root is 2, at index 1 of 4, 2, 5, so 4 is its left child and 5 is its right child. The shape string is 1(2(4(null,null),5(null,null)),3(null,null)). This answer was checked by running the code in this lesson.

Build the tree from preorder 1, 2, 3 and inorder 2, 3, 1. Write its shape string.

Show the answer

The root is 1, at inorder index 2. The left side is 2, 3 (2 nodes), and the right side is empty. The left preorder block is 2, 3. Its root is 2, at index 0 of 2, 3, so its left side is empty and 3 is its right child. The shape string is 1(2(null,3(null,null)),null). This answer was checked by running the code.

Give two different trees that have the same preorder list. Then give the inorder list of each, and explain why the two inorder lists tell them apart.

Show the answer

Tree A has root 1 with a left child 2. Tree B has root 1 with a right child 2. Both have preorder 1, 2. Tree A has inorder 2, 1, because the left child comes before the root. Tree B has inorder 1, 2, because the root comes before the right child. The two inorder lists differ, so the pair of lists identifies one tree.

Change build_tree so that a value missing from the inorder list raises a ValueError with a message that names the value. Run it on preorder 1, 9 and inorder 1, 2.

Show the answer

Replace the lookup in build with this code:

if root_val not in index_of:
    raise ValueError(f"value not in inorder: {root_val}")
mid = index_of[root_val]

Running the build on preorder 1, 9 and inorder 1, 2 raises ValueError with the message value not in inorder: 9. The check happens at the first call, for the value 1, which is found. The second call, for 9, is the one that fails. This answer was checked by running the code.

Summary

The first item of a preorder block is the root. The inorder list shows how many nodes lie on each side of it.
Each call needs a start in preorder and a start and end in inorder. The left block starts at pre_start + 1, and the right block starts after it, at pre_start + 1 + left_size.
One list does not describe one tree. Preorder gives the root, and inorder gives the split.
A dictionary from value to inorder position makes each root lookup a single step, so the build takes O(n) time.
Duplicate values make the input ambiguous, and mismatched list lengths or missing values cause errors.

Build a tree from preorder and inorder in Python

Why this lesson matters

The two walks

Why one list is not enough

The idea, step by step

The ranges

Finding the root quickly

The code

Example 2: a chain

Example 3: a counted search versus a dictionary

Common mistakes

Passing the wrong start to the right side

Duplicate values

Lists of different lengths

A value that is not in inorder

Searching inorder with a loop

Practice

Summary

Stuck? Ask the tutor