Postorder traversal visits the nodes of a binary tree in the order left subtree, right subtree, node, so every node comes after the nodes below it and the root comes last. It takes O(n) time for n nodes, recursively or with two stacks. This page explains how it works, with a step-by-step animation of the two-stack iterative version from the VisiGrab app.
// how postorder traversal works
Postorder traversal, also written post-order or post order, visits every node of a binary tree in the order left subtree, right subtree, node: LRN. The rule holds at every node, so each node comes after all the nodes below it, hence the name: post means after. The root always comes last, and the first node visited is a leaf.
Postorder is one of the three depth-first orders, with preorder (node, left, right) and inorder (left, node, right). The tree need not be a binary search tree: postorder follows the links and never looks at the keys.
The app's walkthrough uses the iterative two-stack method, which works without recursion. It keeps two stacks: the first holds the nodes still to explore, and the second collects them in the reverse of postorder.
1. Start: push the root onto the first stack.
2. Move the top node: pop the first stack and push that node onto the second stack. This is not a visit yet.
3. Push its children: push the node's left child, then its right child, onto the first stack, skipping a missing child. The right child is now on top, so it moves next.
4. Repeat: go back to step 2 until the first stack is empty. The second stack then holds every node, with the root at the bottom.
5. Visit: pop the second stack node by node and visit each one. The nodes come out in postorder, the root last.
The app's code has a recursive and a two-stack version; below, their names lose the Traverse suffix of the listings, and visit prints the node's key. In pseudocode:
recursivePostOrder(node)
if node is none
return
recursivePostOrder(node.left)
recursivePostOrder(node.right)
node.visit()
iterativePostOrder(root)
if root is none
return
stack1 = empty stack
stack2 = empty stack
stack1.push(root)
while stack1 is not empty
node = stack1.pop()
stack2.push(node)
if node.left is not none
stack1.push(node.left)
if node.right is not none
stack1.push(node.right)
while stack2 is not empty
stack2.pop().visit()
recursivePostOrder returns at an empty link and otherwise finishes both calls before node.visit(), so a node is visited only after everything below it. In iterativePostOrder, the first while loop is steps 2 to 4 above and the second is step 5: stack2.pop().visit() pops a node and visits it in one line. Each node is pushed and popped once on each stack: 4n stack operations for n nodes.
The player below runs the two-stack version on the app's default tree, 15 nodes on four levels; the short stack on the left is the first, the tall one on the right the second. It visits 1, 9, 92, 84, 53, 11, 24, 72, 33, 76, 32, 83, 13, 62, 7. No node is visited until the first stack is empty: after the opening, 30 steps push nodes onto the first stack and move them to the second, and all 15 visits come at the end.
The three depth-first orders follow the same route down the links, visit every node once in O(n) time, and differ only in when a node is visited. Postorder is depth-first search on a tree, recording each node when the search leaves it for good. Level order is the breadth-first one: it takes nodes from a queue, level by level.
Not quite: postorder is the reverse of a preorder that takes the right child first (node, right, left), and that is why two stacks work. On the player's tree that order is 7, 62, 13, 83, …: the order in which the first stack hands out the nodes and the second receives them. A stack gives its items back in reverse, so emptying the second stack turns node, right, left into left, right, node.
Reversing the true preorder, 7, 24, 92, …, gives 83, 32, 13, 33, … instead: right, left, node, the mirror image of postorder, with the right subtree first. That is also why the push order matters. Pushing the right child first, as iterative preorder does, would fill the second stack with the preorder and hand back this mirror image.
The one-stack version goes down the left links, as iterative inorder does, and visits the node on top only when it has no right child or its right child was the last node visited, so it keeps one variable for the last visit. Morris traversal needs no stack at all. The app teaches the recursive and the two-stack versions.
Every version visits each node once, so each takes O(n) time for n nodes. They differ in extra space. Recursion keeps one path from the root on the call stack, O(h) for a tree of height h, and so does the one-stack version on its own stack. The height ranges from about log2 n in a balanced tree to n − 1 in a chain, and a very deep tree can overflow the call stack. In the two-stack version the first stack also stays within O(h), at most four nodes on the player's tree, but the second ends up holding all n: O(n). Morris traversal needs only O(1).
The app shows the recursive and the two-stack versions in all three languages, and its info dialog says what deleting a tree takes in each.
Note
In C++ every node allocated with new must be deleted explicitly, and a postorder walk is the natural way to do it: each node is deleted after its children. In Java and Python, setting the root to null or None is enough: the garbage collector reclaims every node that can no longer be reached.
The full source code is on GitHub, in Python, Java and C++.
Postorder fits any task in which a node needs its children done first.
// in the app
In VisiGrab, postorder runs on the default tree or on one you build, with both stacks on screen and a message for each step.
Custom opens a tree editor with four levels and room for 15 nodes. Set a white node's key from 0 to 99, or delete a node with everything below it, and the walk starts over on your tree.
Preorder, inorder and level order walk the same default tree, each in its own color: the first two with one stack, level order with a queue.
The info dialog defines postorder and its use for deleting a tree, in a version for each code language you pick.
The recursive version and the two-stack one in each language, with a note on why popping the second stack gives postorder, and a link to the full source on GitHub.
Six questions with an explanation for every option: the order, the name, the last node, the second stack's job, which child goes on first, and what the three depth-first orders share.
Binary Search Tree, AVL Tree and Red-Black Tree build trees by insertion and deletion, and Stack shows push and pop, the two operations this walk is built on.
// build your own
Download VisiGrab to watch both stacks fill and empty on the default tree, then build a tree of your own and walk it in postorder.
Postorder traversal is one of 30+ topics. See them all