Build a tree from inorder and postorder in Python

Why this matters

A binary tree can be written down as a list of its values in a fixed order. Parsers, file formats and debugging tools often store a tree this way. Sometimes the list is all you get back, and you need the tree again. Another lesson in this module rebuilds a tree from its preorder and inorder lists. This lesson uses the inorder list and the postorder list instead. The method is close to that one, but the postorder list is read from the other end, and that changes which value is the root at each step.

If the words preorder, inorder and postorder are new to you, the list below covers what this lesson needs.

Words you will need

• Binary tree: a tree where each node has at most two children, called left and right. A node is a box that holds one value and two links to its children.
• Root: the top node. It has no parent.
• Leaf: a node with no children.
• Subtree: a node together with everything below it. Every node is the root of its own subtree.
• Inorder: visit the left subtree, then the node, then the right subtree. Write the value down when you visit the node.
• Postorder: visit the left subtree, then the right subtree, then the node.
• Index: the position of an item in a list, counting from 0.
• Range: the part of a list from one index to another, with both ends included. The range 2 to 4 means the items at indexes 2, 3 and 4.
• Dictionary: a table that stores key and value pairs and finds a key in about one step. In Python it is written with curly brackets, and dict.get(key) returns None for a missing key instead of raising an error.
• Recursion: a function that calls itself on a smaller part of the problem, until it reaches a case that needs no more calls.

The method in this lesson assumes that every value in the tree is different. The mistakes section shows what can go wrong when values repeat.

Reading the two lists

Start with a small tree. Here it is drawn as a picture.

        3
       / \
      9   20
         /  \
        15   7

The root is 3. Its left child is 9, a leaf. Its right child is 20, which has two leaf children, 15 on the left and 7 on the right.

Now write the lists that this tree produces.

• Inorder: 9, 3, 15, 20, 7. The root 3 sits between its left subtree (just 9) and its right subtree (15, 20, 7).
• Postorder: 9, 15, 7, 20, 3. The root comes last. Just before it is the right subtree (15, 7, 20), and before that is the left subtree (9).
• Preorder, for comparison: 3, 9, 20, 15, 7. The root comes first.

Two facts from these lists do most of the work.

1. In postorder, the last value is always the root of the whole tree. In the example, the last value is 3.
2. In inorder, the root splits the list into two parts. Everything before the root belongs to the left subtree, and everything after it belongs to the right subtree. In the example, 3 is at index 1, so the left subtree is the item before it (9), and the right subtree is the items after it (15, 20, 7).

With these two facts, the rebuild has a simple outline. Take the last value of the postorder list as the root. Find that root in the inorder list. Split the inorder list into a left part and a right part. Build the left subtree from the left part and the right subtree from the right part. The only remaining question is which part of the postorder list each subtree uses. That is the question the next section answers.

The key idea: read postorder from the end

Postorder lists the left subtree, then the right subtree, then the root. Read it from the end, and the order becomes: root, then the right subtree in reverse, then the left subtree in reverse.

Look at the example again. The postorder list is 9, 15, 7, 20, 3. Reading from the end gives 3, 20, 7, 15, 9. The first value is the root, 3. The next block, 20, 7, 15, is the right subtree in reverse. The last block, 9, is the left subtree.

So this is the rule for the code. Take the next value from the end of the postorder list as the root of the current subtree. Then build the right subtree first. After the right subtree is finished, the next value from the end is the root of the left subtree.

The order matters. If the code built the left subtree first, the next value from the end would belong to the right subtree, and the tree would come out wrong or the code would run out of values.

The code keeps one pointer, an index that marks the next value to read. The pointer starts at the last index of the postorder list. Each call reads the value at the pointer, uses it as the root, and moves the pointer one step to the left. Because each value is read exactly once, the pointer always points at the right value for the subtree being built.

Worked example 1 step by step

The code takes two arguments: the inorder list and the postorder list. The method build takes a range of the inorder list, in_lo to in_hi. Each call builds the subtree whose inorder values are inside that range.

For the example, the inorder list is 9, 3, 15, 20, 7 (indexes 0 to 4). The postorder list is 9, 15, 7, 20, 3 (indexes 0 to 4). The pointer starts at 4.

Here is what happens in order.

1. Call 1 has the range 0 to 4. It reads 3 from the end of postorder and moves the pointer to index 3. It finds 3 in inorder at position 1. It then builds the right range, 2 to 4, before the left range.
2. Call 2 has the range 2 to 4. It reads 20 and moves the pointer to index 2. The position of 20 is 3. It builds its right range, 4 to 4, first.
3. Call 3 has the range 4 to 4. It reads 7 and moves the pointer to index 1. Its right range is 5 to 4, which is empty. Its left range is 4 to 3, which is also empty. An empty range returns no node, so 7 is a leaf.
4. Back in call 2, the left range is 2 to 2. Call 4 reads 15 and moves the pointer to index 0. Both of its ranges are empty, so 15 is a leaf.
5. Back in call 1, the left range is 0 to 0. Call 5 reads 9. Its ranges are empty, so 9 is a leaf.

At the end the pointer is at -1, which means every value of the postorder list was read exactly once. The tree that results has 3 at the root, 9 on the left, and 20 on the right with 15 and 7 under it. That is the tree from the picture.

Why the ranges are right

Each call splits its range at the root's position, mid:

• The left range is in_lo to mid - 1. It has mid - in_lo values.
• The right range is mid + 1 to in_hi. It has in_hi - mid values.

Both ranges stay inside the parent's range. Their sizes add up to the size of the parent's range minus the root itself. In call 1, mid is 1, so the left range has 1 value (index 0) and the right range has 3 values (indexes 2 to 4). That is 1 + 3 = 4, which is the 5 values in the range minus the root.

A range where in_lo is greater than in_hi is empty. A leaf has an empty left range and an empty right range. The code checks for this at the top of build and returns None, which means no node. Without that check, a leaf would take one more value from the postorder list, and that value belongs to some other subtree.

The lookup from value to inorder position is built once, before the recursion starts. Each call then finds the position of its root in about one step, instead of scanning the inorder list.

The code

The code below is the whole program used to check the examples in this lesson. It builds the three examples, prints the preorder list of each rebuilt tree, and shows the two error messages.

Output:

example 1: preorder = [3, 9, 20, 15, 7]
example 2 (right chain): preorder = [1, 2, 3, 4]
example 3: preorder = [1, 2, 4, 5, 3, 6, 7]
bad value: value 4 is not in inorder
bad lengths: lengths differ: 3 and 2

The first output line is the tree from the worked example. Its preorder is 3, 9, 20, 15, 7, which matches the picture.

The class Builder holds the state that the recursion needs: the postorder list, the lookup dictionary, and the pointer. Keeping that state in an object means the method does not need global variables. The function build_tree is the entry point that a caller uses. The pointer is stored as self.post_index, so each call changes the same value. A plain integer passed into a function would be copied, and the change would be lost when the call ends.

Worked example 2: a right chain

Now take the inorder list 1, 2, 3, 4 and the postorder list 4, 3, 2, 1. Here the tree has no left children at all.

The pointer starts at index 3, which holds 1. So the root is 1. Its position in inorder is 0, which means the left range is empty. The right range is 1 to 3, which holds 2, 3 and 4. The pointer is now at index 2, which holds 2. So the next root is 2, and so on. The result is a chain where each node has only a right child.

    1
     \
      2
       \
        3
         \
          4

The program printed example 2 (right chain): preorder = [1, 2, 3, 4], which matches the chain. A chain is the simplest case for the code, but it shows something useful. The recursion goes one level deeper for each value. A very long chain therefore uses a deep call stack. Python's default recursion limit is 1000 calls, so a chain of 1,000 values fails with a RecursionError, while a chain of 900 values works. The method is correct for any tree, but a very deep tree needs a different approach to avoid that limit, such as the iterative walks from earlier lessons in this module.

Worked example 3: a bigger tree

Here is a tree with seven values. The inorder list is 4, 2, 5, 1, 6, 3, 7 and the postorder list is 4, 5, 2, 6, 7, 3, 1.

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

The postorder list has indexes 0 to 6: 4, 5, 2, 6, 7, 3, 1. The pointer starts at 6.

1. Call with the range 0 to 6 reads index 6, which is 1. The root is 1, at inorder position 3. It builds the right range 4 to 6 first.
2. Call with the range 4 to 6 reads index 5, which is 3. The root is 3, at inorder position 5. It builds its right range, 6 to 6, first.
3. Call with the range 6 to 6 reads index 4, which is 7. It is a leaf.
4. Back in the call with the range 4 to 6, the left range is 4 to 4. It reads index 3, which is 6. It is a leaf.
5. Back in the root call, the left range is 0 to 2. It reads index 2, which is 2. The root is 2, at inorder position 1.
6. Its right range is 2 to 2. It reads index 1, which is 5. It is a leaf.
7. Its left range is 0 to 0. It reads index 0, which is 4. It is a leaf.

The pointer is at -1 at the end, and all seven values were used. The program printed example 3: preorder = [1, 2, 4, 5, 3, 6, 7], which matches the drawing.

Checking the result

A rebuilt tree should give back the same lists. The check is simple. Take a tree, write its inorder and postorder lists, rebuild the tree from them, and compare the preorder lists of the original and the rebuilt tree. If they are equal, the rebuild is right for that tree.

A separate random test (not listed here) makes 2000 random trees with 1 to 12 values each, and rebuilds each one. Each tree is built with distinct values, the same as the examples. In a Python test run, all 2000 trees passed the check. That does not prove the method is right for every tree, but a random test catches most mistakes in the index arithmetic, because the mistakes show up as wrong shapes on some tree.

Common mistakes

Reading postorder from the front

A common first try reads the postorder list from the start, with a pointer that goes up. That is the wrong end. The change looks like this, in the same class as above, where self.post_index starts at 0 and goes up:

root_val = self.postorder[self.post_index]   # wrong: the pointer starts at 0 and goes up
self.post_index += 1

The program with this change still runs without an error. For example 1 it prints a different tree:

example 1: preorder = [9, 15, 3, 7, 20]

The root is 9, which is the first value of postorder, and not the last. There is no error message, so this mistake is easy to miss. Test a small example with a known answer, such as example 1 above, and compare the output by hand.

Building the left subtree first

The code must build the right subtree first. If the left subtree is built first, the pointer reads values that belong to the right subtree, and the pointer eventually runs past the start of the list. The program below swaps the two recursive calls and runs on example 1. 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_left_first(inorder, postorder):
    index = {v: i for i, v in enumerate(inorder)}
    pointer = [len(postorder) - 1]
 
    def build(in_lo, in_hi):
        if in_lo > in_hi:
            return None
        root_val = postorder[pointer[0]]
        pointer[0] -= 1
        mid = index[root_val]
        root = TreeNode(root_val)
        root.left = build(in_lo, mid - 1)
        root.right = build(mid + 1, in_hi)
        return root
 
    return build(0, len(inorder) - 1)
 
 
root = build_left_first([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])

The output is:

Traceback (most recent call last):
  File "main.py", line 26, in <module>
    root = build_left_first([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])
  File "main.py", line 23, in build_left_first
    return build(0, len(inorder) - 1)
  File "main.py", line 20, in build
    root.right = build(mid + 1, in_hi)
                 ~~~~~^^^^^^^^^^^^^^^^
  File "main.py", line 19, in build
    root.left = build(in_lo, mid - 1)
                ~~~~~^^^^^^^^^^^^^^^^
  File "main.py", line 20, in build
    root.right = build(mid + 1, in_hi)
                 ~~~~~^^^^^^^^^^^^^^^^
  File "main.py", line 20, in build
    root.right = build(mid + 1, in_hi)
                 ~~~~~^^^^^^^^^^^^^^^^
  File "main.py", line 15, in build
    root_val = postorder[pointer[0]]
               ~~~~~~~~~^^^^^^^^^^^^
IndexError: list index out of range

The message says that the pointer went below the start of the list. The caret lines under each frame can differ by Python version. In Java this shows up as an index of -1. Python is different here, because a negative index such as -1 is valid in Python and counts from the end of the list. The pointer keeps going down, and the error appears only when it reaches -6, which is past the first value of a five-item list. A bug like this can run for a long time and give a wrong tree before any error. The fix is to put the call for root.right above the call for root.left.

Forgetting to check the lookup result

The lookup index.get(root_val) returns None when the value is not in the inorder list. Python does not turn that None into a number. Two lines later the code tries to add 1 to it, and Python stops with a TypeError. The program below leaves out the check. 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_no_check(inorder, postorder):
    index = {v: i for i, v in enumerate(inorder)}
    pointer = [len(postorder) - 1]
 
    def build(in_lo, in_hi):
        if in_lo > in_hi:
            return None
        root_val = postorder[pointer[0]]
        pointer[0] -= 1
        mid = index.get(root_val)
        root = TreeNode(root_val)
        root.right = build(mid + 1, in_hi)
        root.left = build(in_lo, mid - 1)
        return root
 
    return build(0, len(inorder) - 1)
 
 
build_no_check([1, 2, 3], [1, 2, 4])

The output is:

Traceback (most recent call last):
  File "main.py", line 26, in <module>
    build_no_check([1, 2, 3], [1, 2, 4])
    ~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 23, in build_no_check
    return build(0, len(inorder) - 1)
  File "main.py", line 19, in build
    root.right = build(mid + 1, in_hi)
                       ~~~~^~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The message points at mid + 1, but the real problem is the lookup that returned None two lines earlier. The fix is to check the value before you use it, and to raise an error that names the bad value. The class in the program above does that with if root_val not in self.inorder_index, and its output is bad value: value 4 is not in inorder.

Forgetting the empty-range check

If build does not return None when in_lo is greater than in_hi, a leaf makes an extra call with an empty range. That call still reads the next value from the postorder pointer, so it takes a root that belongs to another subtree. The tree is then wrong, and the error may appear later, far from the real cause.

Trusting the input lengths

The two lists must have the same length. The constructor checks this first, and the output bad lengths: lengths differ: 3 and 2 shows the message. Without the check, the mismatch shows up later as an index error or as a wrong tree, and the message does not point to the real cause.

Repeated values

The method assumes each value appears once. The dictionary keeps only one position for each value, so with repeated values the root may be split at the wrong place. The tree can come out wrong with no error, or the pointer can run out of values. If the input may contain repeats, the method needs a different rule for choosing the root's position, and this lesson does not cover that case.

Practice

Exercise 1. Build the tree for the inorder list 2, 1, 3 and the postorder list 2, 3, 1. Write its preorder list.

Show the answer

The last postorder value is 1, so the root is 1. In inorder, 1 is at position 1, so the left range is the value 2 and the right range is the value 3. The right range is built first and reads 3 from the end of the list. The left range then reads 2. The tree has 1 at the root, 2 on the left, and 3 on the right. The preorder list is 1, 2, 3.

Exercise 2. Build the tree for the inorder list 1, 2, 3, 4, 5 and the postorder list 5, 4, 3, 2, 1. Describe its shape in one sentence.

Show the answer

The root is 1, and it has no left child. Its right subtree is built from 2, 3, 4, 5, and the same thing happens at each level. The tree is a chain of right children from 1 down to 5. Every node has at most one child, and that child is on the right.

Exercise 3. Build the tree for the inorder list 1, 2, 3 and the postorder list 1, 3, 2. Write its preorder list.

Show the answer

The last postorder value is 2, so the root is 2. In inorder, 2 is at position 1. The right range is the value 3, and the pointer now points at index 1, which holds 3. The left range is the value 1, read at index 0. The tree has 2 at the root, 1 on the left, and 3 on the right. The preorder list is 2, 1, 3.

Exercise 4. In the call build(in_lo, in_hi), once the root's position mid is known, write an expression for the number of values in the left subtree and an expression for the number in the right subtree.

Show the answer

The left subtree has mid - in_lo values, which are the indexes from in_lo to mid - 1. The right subtree has in_hi - mid values, which are the indexes from mid + 1 to in_hi. For the range 0 to 4 with mid equal to 1, the left subtree has 1 value and the right subtree has 3 values. Together with the root, that is 5 values, which is the size of the range.

Exercise 5. Why does the code build the right subtree before the left subtree? Explain it using the postorder list.

Show the answer

The pointer reads the postorder list from the end. After the root is read, the next block going backwards holds the values of the right subtree, and the block after that holds the values of the left subtree. If the code built the left subtree first, the pointer would read the values of the right subtree while building the left subtree, and every later root would be wrong. Building the right subtree first makes the pointer read each block in the order it sits in the list.

Summary

• In postorder, the last value is the root. Read the list from the end, and the first value you read is the root of the current subtree.
• The inorder list splits at the root. Everything before the root is the left subtree, and everything after it is the right subtree.
• Build the right subtree before the left subtree, because the pointer reads the postorder list from the end.
• Check that each range is not empty before taking a root, and check that each root exists in the inorder list.
• Check the input lengths first. The error messages from this lesson show which check failed.