Iterative postorder with one stack in Python

Why this matters

Postorder means: visit the left subtree, then the right subtree, then the node itself. Every child is finished before its parent is touched. That order is useful. Evaluating an arithmetic expression stored as a tree needs the values of both operands before the operator can be applied. Computing the size or the height of a tree needs the answers for the children first. In a language where you clean up memory yourself, deleting a tree means deleting the children before the parent that points to them.

The previous lesson used a stack for preorder and inorder. Those two orders can be done with a simple rule for each step: push or visit, and then move on. Postorder is harder. When you first reach a node, you cannot visit it, because its right subtree has not been done yet. You have to leave the node on the stack, go to the right side, and come back to it later. The question at each step is therefore: has this node's right side been finished already? The answer is kept in one extra variable, which this lesson builds up step by step.

Recursion handles this question for you, because each call waits for its child calls to return. With a stack, you answer the question yourself.

The tree we will use

It is the same tree as in the previous lesson: 1 at the root, 2 and 3 as its children, 4 and 5 under 2, and 6 under 3 on the right.

        1
       / \
      2   3
     / \   \
    4   5   6

The node class and the builder are the same as before:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def build_sample_tree():
    n1 = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n6 = TreeNode(6)
    n1.left = n2
    n1.right = n3
    n2.left = n4
    n2.right = n5
    n3.right = n6
    return n1

The expected postorder for this tree is 4 5 2 6 3 1. Each node appears after both of its children.

The idea: go left, then look before you pop

Start with the same walk you used for inorder. Go as far left as possible, pushing every node. When you cannot go further left, the top of the stack is the deepest node on the left side. Here the trick starts. Do not pop it yet. Use stack[-1], which looks at the top without removing it, and ask two questions:

1. Does this node have a right child?
2. Did we just come back from that right child?

If the node has a right child and we have not come back from it, go right. Then walk into the right child, and the next round of pushes will handle its subtree. If the node has no right child, or we have already finished its right child, then both sides are done. Pop the node and visit it.

The variable that answers question 2 is called last_visited. Every time you pop and visit a node, store it in last_visited. When you come back to a parent, last_visited is the child you finished most recently. If that child is the parent's right child, the parent is ready to be visited. If the child is the left one, the parent's right side still needs to be walked.

Here is the function. It prints a line for each push, each move to the right, and each visit, so the steps can be traced. The show helper prints the stack from top to bottom, as in the previous lesson:

The show helper uses reversed to start from the right end of the list, which is the top. Python compares the nodes with is, which asks whether two names point at the same object. That is the test we want for last_visited, because two different nodes can never be the same object.

Example 1: postorder of the sample tree

The program above prints this trace for the sample tree:

push 1 -> stack [1]
push 2 -> stack [2, 1]
push 4 -> stack [4, 2, 1]
pop  4: both sides done, visit -> stack [2, 1]
peek 2: right child 5 not done, go right
push 5 -> stack [5, 2, 1]
pop  5: both sides done, visit -> stack [2, 1]
pop  2: both sides done, visit -> stack [1]
peek 1: right child 3 not done, go right
push 3 -> stack [3, 1]
peek 3: right child 6 not done, go right
push 6 -> stack [6, 3, 1]
pop  6: both sides done, visit -> stack [3, 1]
pop  3: both sides done, visit -> stack [1]
pop  1: both sides done, visit -> stack []
result: [4, 5, 2, 6, 3, 1]

Walk through the first part. The first three pushes walk down the left side: 1, then 2, then 4. Node 4 has no children. Its right child is None, so the if is false and the else branch pops 4 and visits it. last_visited is now 4.

The next round starts with 2 on top of the stack. Node 2 has a right child, 5, and last_visited is 4, which is not 5. So the code goes right, and the next pushes handle 5. Node 5 is a leaf, so it is popped and visited. Now last_visited is 5.

Back at 2. Its right child 5 is the same object as last_visited, so the if is false. Node 2 is popped and visited. The order so far is 4 5 2, which is the left subtree of 1 in postorder.

Node 1 is on top now. Its right child is 3, which is not last_visited (that is 2). So the code goes right to 3. Node 3 has the right child 6, so it goes right again. Node 6 is a leaf and is visited. Then node 3 is visited, because its right child 6 is now last_visited. Last, node 1 is visited, because its right child 3 is last_visited.

The result is [4, 5, 2, 6, 3, 1]. Every node comes after its children.

Why the check compares to last_visited

Look at node 2 again. The stack[-1] look at 2 happens twice: once before it goes right, and once after it comes back from 5. The first time, last_visited is 4 and the right child is 5, so the code goes right. The second time, last_visited is 5, which is the right child, so the code pops. The same node, with the same right child, gets two different answers. What changed is last_visited, and that is the only memory the function needs.

This also shows why the method is fast. A node with a right child is looked at twice: once before the walk goes right, and once after the walk comes back. A leaf is looked at once, because it is popped straight away. Every node is therefore looked at at most twice and pushed once, so the work grows with the number of nodes.

Example 2: subtree sums, where order decides the answer

Postorder is the right order for any question where a node's answer depends on its children's answers. A useful example is the sum of all values in each node's subtree. The subtree of node 2 is the nodes 2, 4 and 5, so its sum is 2 + 4 + 5 = 11.

The function below does the same walk as postorder. When it visits a node, both children have already been visited, so their sums are in a dictionary. It adds the node's value to the two child sums and stores the total:

def subtree_sums(root):
    sums = {}
    stack = []
    current = root
    last_visited = None
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        top = stack[-1]
        if top.right is not None and top.right is not last_visited:
            current = top.right
        else:
            stack.pop()
            left_sum = sums[top.left] if top.left is not None else 0
            right_sum = sums[top.right] if top.right is not None else 0
            sums[top] = top.val + left_sum + right_sum
            last_visited = top
    return sums

The dictionary uses the node object as its key. Python allows any object with the default behaviour as a key, and it compares such keys by identity, which means the same object. Two different nodes that hold the same value are two different keys. That is the behaviour we want.

The sum for each node of the sample tree is:

node 1: 21
node 2: 11
node 3: 9
node 4: 4
node 5: 5
node 6: 6

Check node 1 by hand. The whole tree sums to 1 + 2 + 3 + 4 + 5 + 6 = 21, and the stored value matches. Check node 3: it is 3 plus node 6, so 9.

The code depends on the order. If the function visited node 1 before node 2, the dictionary would not yet hold a sum for node 2, and sums[top.left] would raise a KeyError. Postorder makes sure that never happens, because a node is visited only after both of its children.

A preorder walk gives the parent first, so the same code would fail on any tree with children. This is the clearest case for choosing postorder: when the answer for a node is built from the answers below it.

Example 3: a node with only a right side

The sample tree has a left child at every step on the way down, so the walk always starts by going left. A tree can also have a node with no left child at all. This example shows that case. Node 1 has no left child and a right child 2. Node 2 has a left child 3.

    1
     \
      2
     /
    3

Here is the code that builds it, followed by a call to the postorder function from above. It is meant to go in the same file as the function, after it:

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.right = b
b.left = c
print("result:", postorder(a))

The trace from a real run is:

push 1 -> stack [1]
peek 1: right child 2 not done, go right
push 2 -> stack [2, 1]
push 3 -> stack [3, 2, 1]
pop  3: both sides done, visit -> stack [2, 1]
pop  2: both sides done, visit -> stack [1]
pop  1: both sides done, visit -> stack []
result: [3, 2, 1]

The first push puts 1 on the stack. Node 1 has no left child, so the inner while stops straight away. The look at the top finds 1 with a right child, 2, and last_visited is still None, so the code goes right. That is the first move in this tree, and it happens before any node is visited.

Node 2 is pushed, and then the walk to its left pushes 3. Node 3 is a leaf, so it is popped and visited first. Now the top is node 2. Its right side is None, so node 2 is popped and visited. Last, node 1 is on top. Its right child 2 is the node we just visited, so the check is false, and node 1 is popped and visited.

The output is 3 2 1. The rule is the same as for the sample tree: children first, root last. The function does not need to know which side a child is on. It only needs to know whether that child has just been finished.

Example 4: a left chain of four nodes

A left chain has no right children. The last_visited check is never needed for the right side, but the code still runs the same way. Here is the trace of postorder on a chain of four nodes:

push 1 -> stack [1]
push 2 -> stack [2, 1]
push 3 -> stack [3, 2, 1]
push 4 -> stack [4, 3, 2, 1]
pop  4: both sides done, visit -> stack [3, 2, 1]
pop  3: both sides done, visit -> stack [2, 1]
pop  2: both sides done, visit -> stack [1]
pop  1: both sides done, visit -> stack []
result: [4, 3, 2, 1]

All four nodes are pushed first. Node 4 is popped at once, because it has no right child. Each node after that has no right child either, so each is popped in turn. The bottom of the chain comes out first, which is the rule of postorder: the deepest child is visited before its parent.

An empty tree needs no special code. If root is None, the outer while does not run and the result is an empty list.

postorder: []

Common mistakes

Forgetting last_visited

The most common error is to write the check as top.right is not None only. That version sends the walk back to the right child again and again, because it never learns that the right side is done. The program below has that bug. It stops after 30 steps so that it cannot run forever. The code is written with a step counter for that reason.

Here is the real output:

steps used: 30
[4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

The list starts 4, 5, and then 5 again and again. It never visits 2, 3, 6 or 1. Node 5 is a leaf, but without last_visited the code goes back to 5 after every pop. The fix is the line top.right is not last_visited in the check, together with the line last_visited = top after each visit. If a postorder result has repeated values, or fewer values than there are nodes, look for a missing last_visited update first.

Popping before the right side is done

Some people try to pop the node at the first look, to make the code simpler. Once the node is popped, its right side has nowhere to come back to, and the node is visited too early. For the sample tree, that gives a result that starts with 4 2 instead of 4 5 2. The node must stay on the stack until both children are finished.

Using pop where a look is needed

stack[-1] leaves the node on the stack. stack.pop() removes it. In this method you need both: stack[-1] to look at the node while its right side is still pending, and stack.pop() once you decide to visit it. Calling pop at the first look removes the node too early, as described above.

Looking at an empty stack

stack[-1] on an empty list raises an IndexError. The outer loop protects this case, because it runs only while current is not None or the stack is not empty. If you change the loop condition, check that the stack is not empty before the look.

Practice

Exercise 1

Here is the tree with four nodes from the previous lesson. The root is 10. Its left child is 5, and 5 has a left child 2. The root has a right child 15. Write down the postorder of this tree.

Show the answer

The postorder is 2 5 15 10. Node 2 is the deepest left node, so it comes first. Node 5 comes after its left child. Node 15 is the right child of the root and is finished before the root. The root comes last.

Exercise 2

Add a node 7 as the right child of node 4 in the sample tree. What is the postorder of the new tree? Give the answer first, then check it by running the code.

Show the answer

The postorder is 7 4 5 2 6 3 1. Node 4 now has the right child 7, so 7 is visited before 4. The left subtree of 1 gives 7 4 5 2, and the right subtree of 1 gives 6 3. The root 1 is last.

Exercise 3

Explain in your own words why subtree_sums needs postorder, and why preorder would fail. Use the subtree of node 2 in your explanation.

Show the answer

The sum for node 2 is 2 plus the sums of its children 4 and 5. Those sums must already be in the dictionary when node 2 is handled. Postorder visits 4 and 5 before 2, so they are ready. Preorder visits 2 first, and when it reaches 2 the dictionary has no entries for 4 or 5 yet, so the lookup fails with a KeyError.

Exercise 4

The subtree_sums function stores a sum for every node. Describe how to change it so that it stores the number of nodes in each subtree instead. Which line changes, and what is the new value for node 1 in the sample tree?

Show the answer

Replace the calculation with 1 + left_count + right_count, where the child counts come from the dictionary in the same way as the sums. Only the expression that is stored changes. The value for node 1 is 6, because the sample tree has six nodes. The value for node 2 is 3, because its subtree is 2, 4 and 5.

Exercise 5

Explain what happens if the line last_visited = top is removed from the postorder function, using the sample tree as the example. You do not need to write the full trace. Describe the first point where the result goes wrong.

Show the answer

Without that line, last_visited stays None. After node 4 is popped, the code at node 2 sees that its right child 5 is not None and is not last_visited, so it goes right to 5 again. The function then pushes 5 a second time, visits 5 again, and returns to 2 with the same problem. The first wrong value in the result is a repeated 5, and the loop never ends, which is the same kind of failure shown in the common mistakes section.

Summary

• Postorder visits the left subtree, then the right subtree, then the node. Each node comes after its children.
• Look at the top of the stack with stack[-1]. Pop only when both children are finished.
• The last_visited variable tells you whether you have just come back from the right child.
• A function that needs a child's answer before the parent's answer can use postorder, for example a subtree sum.
• Missing the last_visited update gives repeated values in the result. Check it first when the output looks wrong.