Postorder Traversal, step by step.

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

What is postorder traversal? Left, right, root

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.

Iterative postorder traversal using two stacks, without recursion

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.

Postorder traversal pseudocode: recursive and iterative

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.

Postorder traversal example: two stacks step by step

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.

Postorder traversal with two stacks

All steps as text
  1. Take a closer look at how the post-order traversal algorithm works.
  2. Start at the root of the binary tree and push it onto the first stack.
  3. Then pop the node (7) from the first stack and push it onto the second stack. If this node has children, push its left and right children onto the first stack.
  4. Push the left child (24) onto the stack.
  5. Push the right child (62) onto the stack. After that, the next node needs to be popped from the first stack.
  6. Pop (62) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  7. Push the left child (76) onto the stack.
  8. Push the right child (13) onto the stack. After that, the next node needs to be popped from the first stack.
  9. Pop (13) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  10. Push the left child (32) onto the stack.
  11. Push the right child (83) onto the stack. After that, the next node needs to be popped from the first stack.
  12. Pop the node (83) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  13. Pop the node (32) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  14. Pop (76) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  15. Push the left child (72) onto the stack.
  16. Push the right child (33) onto the stack. After that, the next node needs to be popped from the first stack.
  17. Pop the node (33) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  18. Pop the node (72) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  19. Pop (24) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  20. Push the left child (92) onto the stack.
  21. Push the right child (11) onto the stack. After that, the next node needs to be popped from the first stack.
  22. Pop (11) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  23. Push the left child (84) onto the stack.
  24. Push the right child (53) onto the stack. After that, the next node needs to be popped from the first stack.
  25. Pop the node (53) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  26. Pop the node (84) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  27. Pop (92) from the first stack, push it onto the second stack, and if it has children, push the left and right children onto the first stack.
  28. Push the left child (1) onto the stack.
  29. Push the right child (9) onto the stack. After that, the next node needs to be popped from the first stack.
  30. Pop the node (9) from the first stack and push it onto the second stack. Since this node doesn't have any children, the next node needs to be popped from the first stack.
  31. Pop the node (1) from the first stack and push it onto the second stack. At this point the first stack is empty which means all nodes have been processed. The only thing left is to visit the nodes.
  32. Pop the nodes from the second stack one by one and visit them in the post-order sequence.
  33. The traversal is complete once the root is finally visited.
  34. Postorder visited the 15 nodes in the order 1, 9, 92, 84, 53, 11, 24, 72, 33, 76, 32, 83, 13, 62, 7: each node after both of its subtrees, so the root comes last.
Postorder traversal with two stacks. Last step: Postorder visited the 15 nodes in the order 1, 9, 92, 84, 53, 11, 24, 72, 33, 76, 32, 83, 13, 62, 7: each node after both of its subtrees, so the root comes last.

Postorder vs preorder vs inorder: is postorder DFS?

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.

Is postorder the reverse of preorder?

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.

Postorder traversal using one stack, or no stack

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.

Postorder traversal time and space complexity

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).

Postorder traversal in Python, Java and C++

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++.

What is postorder traversal used for?

Postorder fits any task in which a node needs its children done first.

  • Deleting a tree: delete both subtrees, then the node, so no link is ever read from a deleted node.
  • Expression trees and postfix: the postorder of an expression tree is its postfix (reverse Polish) form, so the tree for (3 + 4) × 2 gives 3 4 + 2 ×. Evaluating the tree is a postorder walk too: both operands first, then the operator.
  • Sizes and heights: a node's subtree size is its children's sizes plus 1, and its height is its taller child's height plus 1, counting a leaf as 0. On the player's tree that gives 92 height 1, 24 height 2 and the root 3.
  • Graphs: in a directed acyclic graph, reversed DFS postorder is a topological order, and on any directed graph Kosaraju's algorithm uses the reversed postorder to find strongly connected components.

The default tree here.
Your own 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.

Set keys, cut subtrees

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.

Three more traversals

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.

Why postorder deletes trees

The info dialog defines postorder and its use for deleting a tree, in a version for each code language you pick.

Python, Java and C++

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.

Quiz

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.

Trees and stacks

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.

Children first,
root last.

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