If you know about pre-order traversal you know that it visits the root first and the subtrees later. If you know about in-order traversal you know that it visits the nodes in-order (duh), first the left subtree , then the root and finally the right subtree. The remaining combination is to operate on the root when you’re done with the subtrees. That’s what post-order traversal does.

Let’s see an example of printing all the nodes of a tree using post-order traversal:

Starting from the root the post-order traversal algorithm will visit the left subtree, the right subtree and then return to the root node when it’s done.

Output so far:

We visit the left subtree on node-9 and move on its own subtrees until we find the tree’s leaves.

Output so far:

When we reach node-2 there are no left and right subtrees so we print it

Output so far: 2

Same way with node-5

Output so far: 2, 5

We return to node-9 and since we’re done with its subtrees we print the value 9

Output so far: 2, 5, 9

Back to node-6. We haven’t yet visited its right subtree so on we go

Output so far: 2, 5, 9

Node-4 has no left subtree, so we visit its right-hand one.

Output so far: 2, 5, 9

We visit node-8’s left and right subtrees which are empty and then return to node-8 and print its value

Output so far: 2, 5, 9, 8

Now that we’re done with node-4’s subtrees we print its value

Output so far: 2, 5, 9, 8, 4

We’re done with both subtrees of our tree’s root, node-6. It’s time to print its value too.

Output so far: 2, 5, 9, 8, 4, 6

And that’s it. We’ve traversed the tree In a post-order fashion and have printed its nodes.

The algorithm that achieves that in C++ is the following: