Build a tree from inorder and postorder

Why this matters

A tree is easy to store as text when you write down the order its nodes are visited. A program can save two lists of values, one for inorder and one for postorder, and later rebuild the original tree from them. This is the reverse of a traversal. A traversal turns a tree into a list. This lesson turns the list back into a tree.

The previous lesson in this module rebuilt a tree from preorder and inorder. That method reads preorder from the front. This lesson uses postorder, which ends with the root, so the reading direction changes. The steps are the same in spirit, but the order of the work is different, and most mistakes come from that difference.

This lesson assumes you can write a recursive function, meaning a function that calls itself on a smaller part of the problem. You also need to know what a pointer is and what nullptr means in C++.

Words used in this lesson

A binary tree is a set of nodes. Each node holds one value and may have up to two children, called the left child and the right child. The node at the top, with no parent, is the root. A node with no children is a leaf. A subtree is a node together with everything below it.

A traversal is a rule for visiting every node once and writing down its value. This lesson uses two traversals:

• Inorder visits the left subtree, then the node, then the right subtree.
• Postorder visits the left subtree, then the right subtree, then the node.

In postorder, the node always comes after both of its subtrees. That means the root is always the last value in the postorder list.

A small tree and its two lists

Here is a tree with seven nodes. The values are chosen so that each one is different, which makes the lists easy to read.

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

Walk it with the two rules.

For inorder, start at the root 1. Visit its left subtree first, which is 2 with children 4 and 5. Inside that subtree, visit 4, then 2, then 5. Then visit 1. Then visit the right subtree, which is 3 with children 6 and 7, giving 6, 3, 7. The full inorder list is:

inorder:   4 2 5 1 6 3 7

For postorder, visit the left subtree, then the right subtree, then the node. The left subtree gives 4 5 2. The right subtree gives 6 7 3. Then the root gives 1. The full postorder list is:

postorder: 4 5 2 6 7 3 1

The task is to go the other way. Given the two lists, produce the tree. The rest of the lesson shows how.

The two facts that make it work

There are two facts about these traversals. The method depends on both.

Fact 1: the root is the last value of postorder. The root is visited last in postorder, so the last value in the postorder list is the root. In the example, the last value is 1, and 1 is the root.

Fact 2: inorder splits the values around the root. In inorder, the root sits between its left subtree and its right subtree. Every value to the left of the root in the inorder list belongs to the left subtree. Every value to the right belongs to the right subtree.

Put the two facts together. Take the last postorder value as the root. Find that value in the inorder list. The values before it form the left subtree, and the values after it form the right subtree. Then the same idea applies to each subtree.

Let us trace the example by hand. The last postorder value is 1. In the inorder list 4 2 5 1 6 3 7, the value 1 is at position 3, counting from 0. The values before it are 4 2 5, which is 3 values. The values after it are 6 3 7, which is also 3 values.

Now look at postorder again. Its first 3 values, 4 5 2, are the left subtree, because postorder puts the left subtree first. The next 3 values, 6 7 3, are the right subtree. The last value, 1, is the root. The sizes agree. The left part of postorder has the same length as the left part of inorder, and the right part has the same length as the right part.

Why the right subtree is built first

Postorder is written left, right, root. If you read it from the end, you see root, right, left. This is the important point. Reading from the end gives the root first, then the right subtree, then the left subtree.

The method takes one value from the end of postorder for each node it builds. The first value taken is the root of the whole tree. The next value taken must be the root of the right subtree, because the right subtree's values are the next block when reading backward. So the right subtree must be built before the left subtree. If you build the left subtree first, you take values that belong to the right side.

This is different from the preorder lesson, where the list is read from the front and the left subtree comes first. Here the list is read from the back and the right subtree comes first.

Method: one index that moves backward

There is a simple way to keep track of the postorder values. Keep one index that starts at the last position of postorder, and move it back by one every time you take a root. The index never needs to be reset, because each value is used exactly once.

The inorder list needs a different kind of tracking. Each recursive call works on a range of the inorder list, from a left position to a right position, both included. The root's position in that range splits it into two smaller ranges.

To find a root's position quickly, the code first puts every inorder value into a map, a lookup table from value to position. The lookup then takes about one step, instead of a search through the whole list.

Here is the step-by-step plan for one call:

1. If the inorder range is empty, return nullptr, which means there is no node here.
2. Take the value at the current postorder index as the root, and move that index back by one.
3. Look up the root's position in inorder. Check that the position lies inside the current range.
4. Build the right subtree from the inorder range after the root.
5. Build the left subtree from the inorder range before the root.
6. Return the new node.

Step 4 comes before step 5. That is the rule from the previous section.

Worked example 1: the seven-node tree

Use the lists from the earlier example: inorder 4 2 5 1 6 3 7 and postorder 4 5 2 6 7 3 1. The postorder index starts at 6, the last position. Each row of the table is one call that actually creates a node.

Read the table in order. Call 1 takes the root 1. Its inorder range is the whole list, positions 0 to 6. The root is at position 3. The right range is positions 4 to 6, which holds 6 3 7. The left range is positions 0 to 2, which holds 4 2 5.

Call 2 builds the right subtree first. It takes the next value from postorder, which is index 5, value 3. Its position is 5, and its range is 4 to 6. Its right range is position 6 alone, and its left range is position 4 alone.

Call 3 takes index 4, value 7, at position 6. Its ranges are empty, so it is a leaf. Call 4 takes index 3, value 6, at position 4. It is also a leaf.

Back in call 1, the right subtree is finished, and the postorder index is now at 2. Call 5 takes value 2 for the left subtree, at position 1. Its right range is position 2, and its left range is position 0. Call 6 takes index 1, value 5, at position 2, a leaf. Call 7 takes index 0, value 4, at position 0, also a leaf.

The result is the original tree. Each value was taken from postorder in the order 1, 3, 7, 6, 2, 5, 4 when reading backward, which is the postorder list read from its last value to its first.

Worked example 2: the five-node tree

Here is a second tree, with a different shape. Its inorder list is 9 3 15 20 7, and its postorder list is 9 15 7 20 3.

      3
     / \
    9   20
       /  \
      15   7

The last postorder value is 3, the root. Its inorder position is 1. The left range is position 0, which holds 9. The right range is positions 2 to 4, which holds 15 20 7.

The right subtree is built first. The next postorder value is 20, at index 3. Its inorder position is 3, so its left range is position 2 (value 15) and its right range is position 4 (value 7). The right side takes the next postorder value, 7, which is a leaf. Then the left side takes 15, another leaf. Last, the left subtree of the root takes 9.

The postorder values were taken as 3, 20, 7, 15, 9. Each one is a root in turn, and each step moved the index back by one.

Worked example 3: a chain that leans right

A chain is a tree where every node has only one child. Here every node has only a right child. Take inorder 1 2 3 4 and postorder 4 3 2 1.

The root is 1, the last postorder value. Its inorder position is 0. There is no left subtree, and the right subtree holds 2 3 4. The next root is 2, then 3, then 4. Each of these has an empty left range and a right range that holds the remaining values.

This example has a useful property. The number of nested calls equals the number of nodes in the chain, so a chain of many nodes makes a deep call stack. For this module's small trees that is not a problem, but it is worth knowing that the recursion depth follows the height of the tree.

The code

The code below builds the tree and then checks it by walking the built tree in postorder again. If the result matches the input, the build worked.

The TreeBuilder class keeps the postorder list, the backward index and the map from value to inorder position. The recursive function buildRange does one call of the six-step plan.

#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>
 
struct TreeNode {
    int val;
    std::unique_ptr<TreeNode> left;
    std::unique_ptr<TreeNode> right;
    explicit TreeNode(int v) : val(v) {}
};
 
class TreeBuilder {
public:
    TreeBuilder(const std::vector<int>& inorder, const std::vector<int>& postorder)
        : post_(postorder), postIdx_(static_cast<int>(postorder.size()) - 1) {
        if (inorder.size() != postorder.size()) {
            throw std::invalid_argument("inorder and postorder must have the same length");
        }
        for (int i = 0; i < static_cast<int>(inorder.size()); ++i) {
            if (!indexOf_.emplace(inorder[i], i).second) {
                throw std::invalid_argument("duplicate value in inorder: " + std::to_string(inorder[i]));
            }
        }
    }
 
    std::unique_ptr<TreeNode> build() {
        return buildRange(0, static_cast<int>(post_.size()) - 1);
    }
 
private:
    std::unique_ptr<TreeNode> buildRange(int left, int right) {
        if (left > right) {
            return nullptr;
        }
        int rootVal = post_[postIdx_--];
        auto found = indexOf_.find(rootVal);
        if (found == indexOf_.end()) {
            throw std::invalid_argument("postorder value not in inorder: " + std::to_string(rootVal));
        }
        int mid = found->second;
        if (mid < left || mid > right) {
            throw std::invalid_argument("root " + std::to_string(rootVal) +
                                        " is outside the inorder range [" + std::to_string(left) +
                                        ", " + std::to_string(right) + "]");
        }
        auto node = std::make_unique<TreeNode>(rootVal);
        node->right = buildRange(mid + 1, right);
        node->left = buildRange(left, mid - 1);
        return node;
    }
 
    const std::vector<int>& post_;
    int postIdx_;
    std::unordered_map<int, int> indexOf_;
};
 
void preorder(const TreeNode* node, std::vector<int>& out) {
    if (!node) return;
    out.push_back(node->val);
    preorder(node->left.get(), out);
    preorder(node->right.get(), out);
}
 
void postorder(const TreeNode* node, std::vector<int>& out) {
    if (!node) return;
    postorder(node->left.get(), out);
    postorder(node->right.get(), out);
    out.push_back(node->val);
}
 
void printVector(const std::vector<int>& v) {
    std::cout << "[";
    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << (i + 1 < v.size() ? ", " : "");
    }
    std::cout << "]";
}
 
void runCase(const std::string& name, const std::vector<int>& inorder, const std::vector<int>& post) {
    std::cout << "== " << name << " ==\n";
    try {
        TreeBuilder builder(inorder, post);
        auto root = builder.build();
        std::vector<int> pre;
        std::vector<int> again;
        preorder(root.get(), pre);
        postorder(root.get(), again);
        std::cout << "preorder of built tree: ";
        printVector(pre);
        std::cout << "\n";
        std::cout << "postorder of built tree: ";
        printVector(again);
        std::cout << "\n";
        std::cout << "matches input postorder: " << (again == post ? "yes" : "no") << "\n";
    } catch (const std::invalid_argument& e) {
        std::cout << "invalid input: " << e.what() << "\n";
    }
    std::cout << "\n";
}
 
int main() {
    runCase("example 1: seven nodes", {4, 2, 5, 1, 6, 3, 7}, {4, 5, 2, 6, 7, 3, 1});
    runCase("example 2: five nodes", {9, 3, 15, 20, 7}, {9, 15, 7, 20, 3});
    runCase("example 3: right chain", {1, 2, 3, 4}, {4, 3, 2, 1});
    runCase("bad: root outside range", {1, 2, 3, 4}, {4, 1, 2, 3});
    runCase("bad: value missing", {1, 2, 3}, {1, 2, 9});
    runCase("bad: lengths differ", {1, 2, 3}, {1, 2});
    runCase("bad: duplicate in inorder", {1, 2, 2}, {1, 2, 2});
    runCase("empty", {}, {});
    return 0;
}

Compile and run it with:

g++ -std=c++20 -Wall -Wextra -o build_postorder build_postorder.cpp
./build_postorder

The output, copied from the run on g++ 15.2.0:

== example 1: seven nodes ==
preorder of built tree: [1, 2, 4, 5, 3, 6, 7]
postorder of built tree: [4, 5, 2, 6, 7, 3, 1]
matches input postorder: yes
 
== example 2: five nodes ==
preorder of built tree: [3, 9, 20, 15, 7]
postorder of built tree: [9, 15, 7, 20, 3]
matches input postorder: yes
 
== example 3: right chain ==
preorder of built tree: [1, 2, 3, 4]
postorder of built tree: [4, 3, 2, 1]
matches input postorder: yes
 
== bad: root outside range ==
invalid input: root 2 is outside the inorder range [3, 3]
 
== bad: value missing ==
invalid input: postorder value not in inorder: 9
 
== bad: lengths differ ==
invalid input: inorder and postorder must have the same length
 
== bad: duplicate in inorder ==
invalid input: duplicate value in inorder: 2
 
== empty ==
preorder of built tree: []
postorder of built tree: []
matches input postorder: yes

The first three cases match the trees traced above. The bad cases show the checks at work. The empty case returns nullptr at the first call, so both walks print nothing.

Checking the root and the index bounds

The code makes two checks inside buildRange. Both protect against inputs that cannot describe a tree.

The first check is that the root value exists in inorder. The map lookup returns nothing if the value is missing, and the code throws an error. This catches a postorder list that uses a value the inorder list does not have.

The second check is the bounds check. After the lookup, the root's position must lie inside the current inorder range, from left to right, both included. The range is the part of the inorder list that this subtree is allowed to use. If the root is outside that range, the two lists do not agree.

Here is a real case. Take inorder 1 2 3 4 and postorder 4 1 2 3. The root is 3, at position 2, and that works. The right range is position 3 alone, which holds the value 4. The next postorder value is 2, which is at position 1. Position 1 is outside the range [3, 3]. The code stops with this message:

invalid input: root 2 is outside the inorder range [3, 3]

The bounds check is what stops the program from building a tree with a root that belongs to another part of the tree.

Why does the bounds check need the current range and not only the whole list? A value can be in the whole inorder list and still be in the wrong place for this subtree. The check against the current range catches that case. Checking only that the value exists in inorder is not enough.

Why the values must be unique

The map from value to position has one entry per value. If the same value appears twice in inorder, the map cannot say which position is meant. The constructor checks for this and throws an error. The message in the test run is:

invalid input: duplicate value in inorder: 2

This method needs unique values. Trees with repeated values can still be rebuilt, but then the method needs a different way to tell the copies apart, such as storing positions in a list for each value and using them in order. That is outside this lesson.

Common mistakes

Building the left subtree first. This is the mistake most learners make, because the preorder method builds the left subtree first. With postorder, the right subtree must come first, because the right block is the next one when reading from the end. Here is the result of changing only the order of the two recursive calls, in a copy of the program, run on the seven-node example:

invalid input: root 3 is outside the inorder range [0, 2]

The check turns the problem into an error message.

Taking the root from the front of postorder. Postorder ends with the root, not begins with it. Using post_[0] as the root gives 4 for the seven-node example. The real root is 1, so a tree with 4 at the top cannot be the one the lists describe.

Forgetting the bounds check. The check is short, and it is easy to leave out while the code still seems to work on good input. Without it, a bad input can produce a tree that looks valid but is not the tree the lists describe. The bounds check costs two comparisons per node.

Off-by-one ranges. The left range ends at mid - 1 and the right range starts at mid + 1. The root at mid must be skipped in both. If you write buildRange(mid, right) for the right subtree, the root's position is inside the right range again, so the bounds check may fail, or the tree comes out with the wrong shape. When mid is 0, mid - 1 is -1. This is safe in the code because int is signed and left > right then holds, so the call returns nullptr.

Copying a unique_ptr. Each node owns its children through std::unique_ptr, a pointer that deletes the object it points to when the pointer is destroyed. A unique_ptr cannot be copied, only moved. If you write auto b = a; for two unique_ptr values, the compiler stops with this error (copied from the compile of a small test file with g++ 15.2.0; the line and column depend on the file):

copy_error.cpp:10:14: error: use of deleted function 'std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = TreeNode; _Dp = std::default_delete<TreeNode>]'

To hand the node to another owner, move the pointer with std::move(a), or change the design so the tree is built as values and copied when needed. This lesson moves each subtree into its parent, which the code does with node->right = buildRange(...).

Practice

Exercise 1. Build the tree for inorder 2 1 3 and postorder 2 3 1. Give the root, the left child and the right child.

Show the answer

The last postorder value is 1, so the root is 1. In inorder, 1 is at position 1. The left range is 2, and the right range is 3. So the left child is 2 and the right child is 3. Postorder 2 3 1 agrees: the left child 2, the right child 3, then the root 1.

Exercise 2. For inorder 4 2 5 1 6 3 7 and postorder 4 5 2 6 7 3 1, which node is the left child of the root?

Show the answer

The left child is 2. The root is 1, and its left subtree is the block 4 5 2 in postorder, which ends with 2. Node 2 has children 4 and 5.

Exercise 3. For inorder 9 3 15 20 7 and postorder 9 15 7 20 3, what value does the first call take as the root, and what is its inorder position?

Show the answer

The first call takes the last postorder value, 3. Its inorder position is 1, counting from 0. The program output shows the root is 3 and the preorder starts with 3.

Exercise 4. Can inorder 1 2 3 and postorder 3 1 2 describe a tree? If not, say which check fails and why.

Show the answer

No. The last postorder value is 2, so the root is 2, at inorder position 1. The right range is position 2, which holds 3. The next postorder value is 1. Its inorder position is 0, which is outside the range [2, 2]. The bounds check fails with the message root 1 is outside the inorder range [2, 2]. Running the program on this input prints that message.

Exercise 5. A tree has 7 nodes. How many times does buildRange return nullptr?

Show the answer

Eight. Each node makes two calls, one for its right child and one for its left child, so the 7 nodes make 14 calls, plus the first call from build(). That is 15 calls in total. Seven of them create a node, so 8 return nullptr. In general, a tree with n nodes has n plus 1 empty child slots.

Summary

• Postorder ends with the root, so the last value is always the root of the current subtree.
• Inorder splits the values around the root, and the root's position gives the sizes of the two subtrees.
• Read postorder from the end, which means building the right subtree before the left.
• Keep one backward index into postorder, and pass only inorder ranges through the recursion.
• Check that the root's inorder position lies inside the current range, because a bad root means the lists do not agree.
• Values must be unique for the value-to-position map to work.