Iterative postorder with one stack

Why this matters

Postorder visits a node only after both of its subtrees have been visited. In plain words, children come before their parent. This order is needed when a parent's result depends on its children's results. Deleting a tree from the bottom up, evaluating an arithmetic expression and computing the size of every folder in a file tree all use postorder.

The previous lesson wrote preorder and inorder with a stack. Those two were easy, because each one can be decided the moment a node is first seen (preorder) or after walking left (inorder). Postorder is harder. When the walk first reaches a node, its children have not been visited yet, so the node must wait on the stack. Later it is visited, but only if its right subtree is finished. The program needs a way to tell "I am back from my right child" apart from "I am arriving from above". This lesson shows the one extra variable that makes that possible.

The recursive version is short and is shown below for comparison. Many programmers learn it first.

void postorder_recursive(const Node* node) {
    if (node == nullptr) return;
    postorder_recursive(node->left.get());
    postorder_recursive(node->right.get());
    visit(node);
}

The idea: a stack of waiting parents and one pointer

Think of a line of people waiting at a door. A parent is at the back of the line. The parent cannot go through the door until the two children ahead of them have gone through. The parent stays in the line, and each time a child is done, the parent looks back to see whether the child that just left was the last one it was waiting for.

A stack holds the parents in the line. The top of the stack is the node the walk is currently waiting on. The question at each step is: for the node on top, is its right child finished?

A last-visited pointer answers that question. Call it last. It remembers the node that was most recently visited. When a node is visited, last is set to it. The rule is:

• If the top node has a right child, and that right child is not last, the right child has not been finished yet. Walk into it.
• Otherwise, the top node's right side is done (either there is no right child, or the right child was just finished). Visit the top node, set last to it, and pop it.

The reason this works is that last is the node you just came back from. If you come back from a right child, last equals the top's right child, so the top is ready. If you come back from a left child, last is the left child, which is not the top's right child, so you go right.

A small tree, traced step by step

Use this three-node tree:

      2
     / \
    1   3

Postorder should give 1 3 2. The trace below uses two variables: cur is the node the walk is at, and last is the node most recently visited. The table shows what the program does at each step.

The output is 1 3 2.

Step 7 is the important moment. At that point 2's right child, 3, is the node we just came back from. The pointer last says so, and that is the only signal the code needs.

The program below runs the same steps and prints a line for each action. Compile it and run it. The output is shown after the code.

#include <iostream>
#include <memory>
#include <stack>
#include <vector>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
 
using NodePtr = std::unique_ptr<Node>;
 
NodePtr make(int value, NodePtr left = nullptr, NodePtr right = nullptr) {
    return std::make_unique<Node>(Node{value, std::move(left), std::move(right)});
}
 
std::vector<int> postorder_traced(const Node* root) {
    std::vector<int> out;
    std::stack<const Node*> st;
    const Node* cur = root;
    const Node* last = nullptr;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            std::cout << "push " << cur->value << "  stack size " << st.size() << '\n';
            cur = cur->left.get();
        } else {
            const Node* top = st.top();
            if (top->right != nullptr && top->right.get() != last) {
                std::cout << "peek " << top->value << ": go right to " << top->right->value << '\n';
                cur = top->right.get();
            } else {
                std::cout << "peek " << top->value << ": visit " << top->value << ", pop  stack size "
                          << st.size() - 1 << '\n';
                out.push_back(top->value);
                last = top;
                st.pop();
            }
        }
    }
    return out;
}
 
int main() {
    auto small = make(2, make(1), make(3));
    for (int x : postorder_traced(small.get())) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

push 2  stack size 1
push 1  stack size 2
peek 1: visit 1, pop  stack size 1
peek 2: go right to 3
push 3  stack size 2
peek 3: visit 3, pop  stack size 1
peek 2: visit 2, pop  stack size 0
1 3 2 

Each line in the output matches one row of the table. The peek lines are the moments when the program looks at the top of the stack without removing it. A peek followed by go right means the right subtree is not done. A peek followed by visit means the node is finished.

The function without the trace

The full function is shown below. It is the same logic with the prints removed.

std::vector<int> postorder(const Node* root) {
    std::vector<int> out;
    std::stack<const Node*> st;
    const Node* cur = root;
    const Node* last = nullptr;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left.get();
        } else {
            const Node* top = st.top();
            if (top->right != nullptr && top->right.get() != last) {
                cur = top->right.get();
            } else {
                out.push_back(top->value);
                last = top;
                st.pop();
            }
        }
    }
    return out;
}

The loop has two branches. The first branch (cur != nullptr) is the walk down the left side, which pushes each node as it goes. The second branch (cur == nullptr) looks at the top, decides whether to go right or to finish the top, and never pushes a node itself. The right child is pushed later, when the first branch runs on it.

Here is the complete program for the 7-node tree from the earlier lessons:

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

#include <iostream>
#include <memory>
#include <stack>
#include <vector>
 
struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
 
using NodePtr = std::unique_ptr<Node>;
 
NodePtr make(int value, NodePtr left = nullptr, NodePtr right = nullptr) {
    return std::make_unique<Node>(Node{value, std::move(left), std::move(right)});
}
 
std::vector<int> postorder(const Node* root) {
    std::vector<int> out;
    std::stack<const Node*> st;
    const Node* cur = root;
    const Node* last = nullptr;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left.get();
        } else {
            const Node* top = st.top();
            if (top->right != nullptr && top->right.get() != last) {
                cur = top->right.get();
            } else {
                out.push_back(top->value);
                last = top;
                st.pop();
            }
        }
    }
    return out;
}
 
void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}
 
int main() {
    auto root = make(4,
                     make(2, make(1), make(3)),
                     make(6, make(5), make(7)));
    std::cout << "postorder: ";
    print(postorder(root.get()));
}

Output:

postorder: 1 3 2 5 7 6 4 

The output reads left subtree, then right subtree, then root, at every level. Node 4 comes last, because it is the root.

A chain of right children

A chain is a tree where each node has only one child. The chain below has only right children:

1
 \
  2
   \
    3

Postorder of this chain is 3 2 1. The walk goes down the right side, and nothing is visited until the bottom is reached. Then each node is visited on the way back up. Here is the program that prints it, run from main in a file with the same Node type and postorder function as above:

auto chain = make(1, nullptr, make(2, nullptr, make(3)));
std::cout << "postorder: ";
print(postorder(chain.get()));

Output:

postorder: 3 2 1 

The chain is a useful test case, because a bug in the right-child check shows up immediately. A chain also shows that the stack can hold every node at once: for 1 -> 2 -> 3 the peak is 3. Each node is pushed, and then the walk waits there while its right child is pushed and handled.

A third example: evaluating an expression tree

Postorder fits any problem where a parent's answer needs its children's answers first. An expression tree is a good example. Each leaf is a number. Each inner node is an operator, such as + or *, whose two children are the things it combines. The tree below holds (2 + 3) * 4:

      *
     / \
    +   4
   / \
  2   3

To evaluate the tree, you need the value of 2 + 3 before you can multiply it by 4. In other words, the operator node is handled after both of its children. That is postorder.

The traversal needs a place to keep each node's answer, so this example stores the results in a std::unordered_map, which is a lookup table keyed by the node's address. When a node is visited, its children have already been visited, so their results are in the table. The program below evaluates two expressions. The first is the tree above. The second is ((1 + 2) * (3 + 4)) + 5.

#include <iostream>
#include <memory>
#include <stack>
#include <unordered_map>
 
struct Node {
    char op;  // '+', '*' or 0 for a number
    long long number;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
};
 
using NodePtr = std::unique_ptr<Node>;
 
NodePtr number(long long n) {
    return std::make_unique<Node>(Node{0, n, nullptr, nullptr});
}
 
NodePtr op(char c, NodePtr left, NodePtr right) {
    return std::make_unique<Node>(Node{c, 0, std::move(left), std::move(right)});
}
 
long long evaluate(const Node* root) {
    std::unordered_map<const Node*, long long> result;
    std::stack<const Node*> st;
    const Node* cur = root;
    const Node* last = nullptr;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left.get();
        } else {
            const Node* top = st.top();
            if (top->right != nullptr && top->right.get() != last) {
                cur = top->right.get();
            } else {
                if (top->op == 0) {
                    result[top] = top->number;
                } else if (top->op == '+') {
                    result[top] = result[top->left.get()] + result[top->right.get()];
                } else {
                    result[top] = result[top->left.get()] * result[top->right.get()];
                }
                last = top;
                st.pop();
            }
        }
    }
    return result[root];
}
 
int main() {
    auto tree = op('*', op('+', number(2), number(3)), number(4));
    std::cout << "(2 + 3) * 4 = " << evaluate(tree.get()) << '\n';
 
    auto bigger = op('+',
                     op('*', op('+', number(1), number(2)), op('+', number(3), number(4))),
                     number(5));
    std::cout << "((1 + 2) * (3 + 4)) + 5 = " << evaluate(bigger.get()) << '\n';
}

Output:

(2 + 3) * 4 = 20
((1 + 2) * (3 + 4)) + 5 = 26

Check the second answer by hand. 1 + 2 is 3, and 3 + 4 is 7. Then 3 * 7 is 21, and 21 + 5 is 26. The traversal gives the same result.

The code for the second example uses op and number helper functions, so the tree is easy to write. The expression (2 + 3) * 4 is built as op('*', op('+', number(2), number(3)), number(4)). Reading the call from the inside out gives the same shape as the picture above.

Common mistakes

Mistake 1: leaving out the last-visited check

The most common error is to walk into the right child every time one exists, with no last check:

const Node* top = st.top();
if (top->right != nullptr) {
    cur = top->right.get();
} else {
    out.push_back(top->value);
    st.pop();
}

This code never finishes on a tree that has any right child. Here is what happens on the 3-node tree. The walk visits 1 and pops it. The top is 2, which has a right child, 3, so the code walks into 3. It pushes 3, finds no left child, and pops 3. The top is 2 again. Its right child is still 3, so the code walks into 3 again. The same node is pushed and popped over and over, and the output fills with copies of 3.

We tested a version of this idea with a step counter. It did not finish within 1000 steps, and the stack never held more than 2 nodes. Without a counter, it would run forever. The fix is the last check from the lesson. It tells the code that the right child was already finished, so the parent can be visited.

Mistake 2: setting last at the wrong time

Some programs set last when they go right, instead of when they visit. This is a different mistake from the first one. last must mean "the node visited most recently". If you set it when you walk into the right child, last becomes the right child before that child is done. The check top->right.get() != last then fails for the wrong reason, and the code can visit a parent before its right subtree is finished.

Keep the assignment in the same place as the visit, after out.push_back(...), and nowhere else.

Mistake 3: forgetting the null check on the right child

The code calls top->right.get() and compares it with last. If top->right is null, get() returns a null pointer. Compare that with last, and the walk sets cur to null and then peeks at the same node again, forever. The check top->right != nullptr in the if condition prevents this. Do not remove it when you simplify the code.

Mistake 4: calling pop without a peek

A common shortcut is to pop the top before deciding whether to go right. That removes the parent from the stack, so the code has nothing to come back to. The top must stay on the stack while its right subtree is walked. It is removed only in the else branch, when the node is visited. The st.top() call in the code reads the parent without removing it, and that is why the parent is still there after the walk into the right side.

Practice

Exercise 1: trace a different tree

Trace the postorder walk on this tree. Write the value of cur, last and the stack at each step, in the same form as the table in the lesson. Then write the final output.

      5
     / \
    3   8
   /
  1

Show the answer

The output is 1 3 8 5. The walk goes down the left side: push 5, push 3, push 1. Node 1 has no right child, so visit 1 and set last to 1. Peek at 3. It has no right child, so visit 3, and last becomes 3. Peek at 5. Its right child is 8, and 8 is not last, so walk right. Push 8. Node 8 has no children, so visit 8 and set last to 8. Peek at 5. Its right child 8 is last, so visit 5.

Exercise 2: postorder of a complete tree

Write the postorder output for a complete tree of 15 nodes, with values 1 to 15. The root is 8. Its left child is 4 and its right child is 12. The leaves are the odd numbers from 1 to 15. The rule is: node 4 has children 2 and 6, node 12 has children 10 and 14, node 2 has children 1 and 3, node 6 has children 5 and 7, node 10 has children 9 and 11, and node 14 has children 13 and 15.

Show the answer

The output is 1 3 2 5 7 6 4 9 11 10 13 15 14 12 8. Each subtree is listed before its root. The left subtree of 8 gives 1 3 2 5 7 6 4. The right subtree gives 9 11 10 13 15 14 12. The root 8 comes last.

Exercise 3: count nodes in postorder

Write a function int count_nodes(const Node* root) that uses the postorder pattern from this lesson and returns the number of nodes. It should return 0 for an empty tree. On the 7-node tree, what should it return?

Show the answer

int count_nodes(const Node* root) {
    if (root == nullptr) return 0;
    int count = 0;
    std::stack<const Node*> st;
    const Node* cur = root;
    const Node* last = nullptr;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left.get();
        } else {
            const Node* top = st.top();
            if (top->right != nullptr && top->right.get() != last) {
                cur = top->right.get();
            } else {
                ++count;
                last = top;
                st.pop();
            }
        }
    }
    return count;
}

On the 7-node tree it returns 7. Each node is visited exactly once, and the count increments at each visit.

Exercise 4: evaluate a subtraction tree

Change the evaluate function from the lesson so it also handles -, where a - b is the left result minus the right result. Then evaluate the tree for (10 - 4) * 3. What is the answer?

Show the answer

Add one branch to the operator logic:

} else if (top->op == '-') {
    result[top] = result[top->left.get()] - result[top->right.get()];
}

The tree (10 - 4) * 3 gives (10 - 4) equal to 6, and then 6 * 3 equals 18. The answer is 18.

Exercise 5: what goes wrong without the stack

A student writes postorder with a single variable cur and no stack, and tries to go back up the tree using the parent's address. Explain why this needs a stack for a binary tree when the nodes only store left and right children and no parent pointer.

Show the answer

A node with only left and right pointers has no way to find its parent. Going down is easy, because each node points to its children. Going back up needs a record of the path that was taken. The stack is that record. Each node on the stack is a parent that has been entered but not finished. Without a parent pointer, the program must store the parents somewhere, and a stack is the natural place.

Summary

• Postorder visits both children before the node, so a node waits on the stack until its right subtree is finished.
• The loop has two branches. One walks left and pushes each node. The other peeks at the top and either walks right or visits and pops it.
• The last pointer holds the node visited most recently. If the top's right child is last, the right subtree is done.
• Set last only at the moment a node is visited, and keep the top->right != nullptr check.
• Postorder is the right order whenever a parent's result depends on its children, such as expression evaluation.