Build a tree from preorder and inorder

Why it matters

Some tasks give you a tree as two lists of values, not as a ready-made tree. A test might record two walks over a tree and ask you to rebuild its shape. The problem is to take those two lists and return the tree they came from.

This lesson uses two of the three walks over a binary tree. A binary tree is a set of nodes, where each node has one value and at most two children, a left child and a right child. The first walk is preorder, which visits the node, then its left subtree, then its right subtree. The second walk is inorder, which visits the left subtree, then the node, then the right subtree. The next lesson in this module uses inorder with postorder instead, so this lesson only covers the preorder and inorder pair.

By the end you will know why two walks are needed, how to split the lists, how to find a root's position in constant time with a hash map, and how to check the result.

Why one walk is not enough

Start with a short example. Suppose the preorder list is 1, 2. That list has no clue about which side the 2 is on. The tree could be a root 1 with a left child 2, or a root 1 with a right child 2.

Now add the inorder list. For the first tree, the inorder walk visits the left child first, so the inorder list is 2, 1. For the second tree, the inorder walk visits the root first, so the list is 1, 2. Two lists give two different answers. The inorder list tells you where the root sits among the others, and that is the missing information.

The program in this lesson builds both trees from their lists and prints the shape of each result:

two nodes, 2 on left: preorder 1,2 inorder 2,1 ok
    shape 1,2,#,#,#
two nodes, 2 on right: preorder 1,2 inorder 1,2 ok
    shape 1,#,2,#,#

The shape line uses the same marker format as the serialize lesson before this one. In the shape 1,2,#,#,#, the 2 comes right after the root, and it is followed by two markers that belong to 2, so the 2 is the left child. In the shape 1,#,2,#,#, the first marker says the root has no left child, so the 2 is the right child.

One rule makes the whole method work. This only works when every value in the tree is different. If two nodes share a value, the lists no longer say which copy is which. The code below assumes distinct values, and a later section shows what happens when that rule is broken.

The idea: the first preorder value is the root

Preorder always lists the root first. So the first number in the preorder list is the root of the whole tree, and of every subtree inside it. That gives you a way to start.

Take the classic example. The preorder list is 3, 9, 20, 15, 7 and the inorder list is 9, 3, 15, 20, 7. The root is the first preorder value, which is 3.

Find 3 in the inorder list. It is at position 1, counting from 0. Everything before it in inorder is the left subtree, and everything after it is the right subtree. So the left subtree holds 9, and the right subtree holds 15, 20, 7.

Now the preorder list tells you the rest. After the root, preorder lists the whole left subtree, then the whole right subtree. The left subtree has one value, so the first value after the root in preorder is the left part, which is 9. The remaining three values, 20, 15, 7, are the right part. The size of the left part came from inorder, and that size splits the preorder list into the same two parts.

Here is the tree the two lists describe:

    3
   / \
  9   20
     /  \
    15   7

Work through the two smaller problems. The left subtree has preorder 9 and inorder 9. It is a single node, with no children. The right subtree has preorder 20, 15, 7 and inorder 15, 20, 7. Its first preorder value is 20, the root of that subtree. In inorder, 20 is at position 1 of its own list, so its left part is 15 and its right part is 7. Each part is a single node. The full walk is then done.

The program builds this tree and checks it by walking it back out:

classic: preorder 3,9,20,15,7 inorder 9,3,15,20,7 ok
    shape 3,9,#,#,20,15,#,#,7,#,#

The ok means the rebuilt tree produces the same preorder and inorder lists that went in. The shape line confirms the structure, which is the root 3 with the 9 on its left and the 20 on its right.

The recursive plan

The method repeats the same steps on smaller lists, so it is a recursive method. Every call receives a range of the preorder list and a range of the inorder list. A call does four things:

1. If the preorder range is empty, return no node.
2. Take the first value in the preorder range as the root.
3. Find the root's position in the inorder range.
4. Use the number of values to the left of that position to split both ranges, then make two calls, one for each side.

The ranges are given as start and end positions, and the end position is not included. A range from 0 to 5 covers positions 0, 1, 2, 3 and 4. An empty range has equal start and end positions.

Finding the root's position fast

Step 3 is the slow part if you do it badly. The easy way to find the root in the inorder list is to scan from the start of the range until you see the root's value. A scan can take as long as the range is long. Each node causes one scan, so for a tree of n nodes the total work can reach about n times n, which is written as O(n squared).

A better way is to store the position of every value in a map before the recursion starts. A map from value to position lets each lookup take about the same time, no matter how long the list is. The code uses std::unordered_map, which is a hash map. A hash map finds a key by computing a number from it and looking in that spot, so one lookup takes constant time on average.

Building the map visits each inorder value once, and each node in the rebuilt tree costs one lookup. So the total work is O(n) on average. The Position alias in the code names the type so that it is easy to read.

The code

The function below builds the subtree for one pair of ranges. The wrapper build_tree checks the inputs and builds the map. Both are in the same file as the test program.

using Position = std::unordered_map<int, int>;
 
// Builds the subtree whose preorder values are preorder[pre_lo, pre_hi)
// and whose inorder values are inorder[in_lo, in_hi).
std::unique_ptr<Node> build(std::span<const int> preorder, std::span<const int> inorder,
                            const Position& position, std::size_t pre_lo, std::size_t pre_hi,
                            std::size_t in_lo, std::size_t in_hi) {
    if (pre_lo >= pre_hi) {
        return nullptr;
    }
 
    int root_value = preorder[pre_lo];
    ++lookups;
    std::size_t mid = position.at(root_value);
    if (mid < in_lo || mid >= in_hi) {
        throw std::invalid_argument("inputs do not match");
    }
 
    std::size_t left_size = mid - in_lo;
    auto root = std::make_unique<Node>(root_value);
    root->left = build(preorder, inorder, position,
                       pre_lo + 1, pre_lo + 1 + left_size,
                       in_lo, mid);
    root->right = build(preorder, inorder, position,
                        pre_lo + 1 + left_size, pre_hi,
                        mid + 1, in_hi);
    return root;
}
 
std::unique_ptr<Node> build_tree(const std::vector<int>& preorder, const std::vector<int>& inorder) {
    if (preorder.size() != inorder.size()) {
        throw std::invalid_argument("lengths differ");
    }
 
    Position position;
    for (std::size_t i = 0; i < inorder.size(); ++i) {
        position[inorder[i]] = static_cast<int>(i);
    }
    return build(preorder, inorder, position, 0, preorder.size(), 0, inorder.size());
}

The lookups counter is a global variable in the test file. It counts how many times build looked up a root in the map. It exists only so the program can show the cost, and the real algorithm does not need it.

Read the split carefully. mid is the root's position in the whole inorder list, not in the small range. Because of that, the number of values on the left is mid - in_lo. The left subtree's preorder values start at pre_lo + 1 and run for left_size values. The right subtree's preorder values start just after them. The right subtree's inorder values start at mid + 1, which skips the root.

The std::span parameters are views onto the vectors. They do not copy the data, so passing a range costs the same no matter how big it is. A view has a size and a way to read each element, and that is all the code needs.

Worked example: the classic tree

Trace the classic example through the code, with the ranges written out. The top call gets preorder [0, 5) and inorder [0, 5).

• The root value is preorder[0], which is 3. Its position in inorder is mid = 1.
• The left size is 1 - 0 = 1. The left call gets preorder [1, 2), which is the value 9, and inorder [0, 1), which is the value 9.
• The right call gets preorder [2, 5), which is 20, 15, 7, and inorder [2, 5), which is 15, 20, 7.
• The left call sees root 9 at inorder position 0. Its left size is 0, and both of its child ranges are empty, so it returns a leaf.
• The right call sees root 20 at inorder position 3. Its left size is 3 - 2 = 1, so the left call gets preorder [3, 4) and inorder [2, 3), both holding 15. The right call gets preorder [4, 5) and inorder [4, 5), both holding 7.

That covers all five values, and each one became a node once. The walk visited five real nodes, plus the empty ranges that returned no node.

Worked example: a left chain

A left chain is a tree where each node has only a left child. Its preorder and inorder lists look unusual, which makes it a good test. Take preorder 1, 2, 3 and inorder 3, 2, 1.

The root is 1. In inorder, 1 is at the end, so everything before it is the left subtree. The left subtree is 3, 2. Its preorder part is 2, 3, so 2 is the root of that subtree, and 3 is its left child. The result is a chain going down the left side.

The program prints the rebuilt tree:

left chain: preorder 1,2,3 inorder 3,2,1 ok
    shape 1,2,3,#,#,#,#

The shape reads as root 1, then 2 as its left child, then 3 as the left child of 2. Every right child is a marker.

Worked example: a deeper tree

The third example has seven nodes and two levels of branching. Its preorder list is 10, 5, 1, 7, 15, 12, 20 and its inorder list is 1, 5, 7, 10, 12, 15, 20.

The root is 10. In inorder, 10 is at position 3, so the left subtree has three values, 1, 5, 7, and the right subtree has three values, 12, 15, 20. The preorder list splits the same way. After the root, the first three values, 5, 1, 7, are the left subtree, and the last three, 15, 12, 20, are the right subtree.

The left subtree has root 5. In its inorder list 1, 5, 7, the 5 is in the middle, so 1 is its left child and 7 is its right child. The right subtree has root 15. In its inorder list 12, 15, 20, the 15 is in the middle, so 12 and 20 are its children.

deeper: preorder 10,5,1,7,15,12,20 inorder 1,5,7,10,12,15,20 ok
    shape 10,5,1,#,#,7,#,#,15,12,#,#,20,#,#

The walk-back check confirms that the output matches the input in both orders.

The cost of the map

The test below builds right chains of increasing size and counts the lookups. A right chain has each node as the right child of the one above, so its inorder and preorder lists are the same. The count should equal the number of nodes:

Lookups for a right chain of n nodes:
  n = 1000, lookups = 1000
  n = 2000, lookups = 2000
  n = 4000, lookups = 4000

Each node costs one lookup, so the number of lookups equals n. If the code scanned the inorder list for every root instead, the work would grow much faster. Doubling n would make the scan work about four times larger, which is the O(n squared) cost from earlier.

Checking the input

The wrapper checks the two lists before it does any work. The first check is the length. If the lists have different lengths, they cannot describe the same tree, so build_tree throws. The second check is inside build. If the root's position in inorder falls outside the range the call was given, the lists do not match. That can only happen with bad input, and the code throws rather than building a wrong tree.

The map lookup also has a failure. If a preorder value is not in the inorder list at all, at throws an exception. The mistakes section below shows the messages.

Common mistakes

Using the wrong walk for the root

The root must come from the start of preorder, not from inorder. Inorder puts the root in the middle of the list, so taking the first inorder value gives the leftmost value, which is usually not the root. Using the wrong walk gives a tree that still has the right values but the wrong shape.

Off-by-one in the left size

The left size is the number of values before the root in inorder, which is mid - in_lo. A common error is to add 1 or to forget the start offset. If you use mid alone, the left range is wrong whenever the range does not start at 0.

Copying the lists on every call

A simple version creates a new std::vector for each subtree and copies the values into it. Each copy costs time proportional to its length, and the copies add up to about O(n squared) work on a skewed tree. The code above avoids this by passing start and end positions, so the lists are never copied.

Duplicate values

The method needs every value to be different. If a value appears twice, the map keeps only one position for it. The bad-input test passes the lists 1, 1 for both preorder and inorder:

  error: inputs do not match

The lists are not valid for a tree with two nodes of value 1, and the function reports that. When values repeat, two different trees can give the same two lists, so the lists alone do not say which tree was meant. Check for duplicates before you call the function if the input is not trusted.

Lengths that differ

If the two lists have different lengths, the input is wrong. For example, preorder 1, 2 with inorder 1 gives:

  error: lengths differ

A value missing from the inorder list

If a value appears in preorder but not in inorder, the map has no entry for it. The at function then throws. The example preorder 1, 4 with inorder 2, 1 gives:

  error: unordered_map::at

The message is short, but it tells you that a lookup failed. The fix is to check that both lists contain the same values before the call.

Practice

Exercise 1

Rebuild the tree from preorder 1, 2, 4, 5, 3 and inorder 4, 2, 5, 1, 3. Give its shape in the marker format.

Show the answer

The root is 1. In inorder, 1 is at position 3, so the left subtree is 4, 2, 5 and the right subtree is 3. The left subtree has preorder 2, 4, 5, so its root is 2. In its inorder list 4, 2, 5, the 2 has 4 on the left and 5 on the right. The shape is 1,2,4,#,#,5,#,#,3,#,#.

Exercise 2

Why is the first value of the preorder list always the root of the whole tree?

Show the answer

Preorder visits the node before its children. The whole tree is the first node visited, so its value comes first in the list. The same rule holds for every subtree, which is why the recursion can use the first value of each preorder range as that range's root.

Exercise 3

Rebuild the tree from preorder 1, 2, 3 and inorder 2, 1, 3. Give its shape.

Show the answer

The root is 1, the first preorder value. In inorder, 1 is at position 1, so the left subtree is 2 and the right subtree is 3. The shape is 1,2,#,#,3,#,#.

Exercise 4

For a tree of n nodes, how many times does the code look up a value in the map? Explain why.

Show the answer

It looks up each root once, and every real node is a root of exactly one call. So the count is n. The right chain test prints 1000 lookups for 1000 nodes, 2000 for 2000, and 4000 for 4000. Empty ranges return early and do no lookup.

Exercise 5

What goes wrong if the code takes the root from the last value of preorder instead of the first?

Show the answer

The last preorder value is always a leaf (a node with no children), not the root. Using it as the root splits both lists in the wrong place. The left and right ranges then hold the wrong values, so the rebuilt tree is wrong or the code throws an error.

Summary

• Preorder gives the root as its first value. Inorder shows which values fall to its left and which fall to its right.
• The size of the left part splits both lists into two smaller problems.
• A map from value to inorder position lets each root be found in constant time on average, which gives O(n) time overall.
• Check that the lists have the same length, that the values match, and that the values are distinct.