{"id":170,"date":"2014-05-02T11:08:11","date_gmt":"2014-05-02T11:08:11","guid":{"rendered":"http:\/\/www.dimlucas.com\/?p=170"},"modified":"2017-02-22T11:12:05","modified_gmt":"2017-02-22T11:12:05","slug":"post-order-traversal-of-a-binary-tree-in-c","status":"publish","type":"post","link":"https:\/\/www.dimlucas.com\/index.php\/2014\/05\/02\/post-order-traversal-of-a-binary-tree-in-c\/","title":{"rendered":"Post-order Traversal of a Binary Tree in C++"},"content":{"rendered":"

If you know about pre-order traversal<\/a> you know that it visits the root first and the subtrees later. If you know about in-order traversal<\/a> 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.<\/p>\n

Let’s see an example of printing all the nodes of a tree using post-order traversal:<\/p>\n

\"binarytree\"<\/p>\n

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.<\/p>\n

Output so far<\/strong>: <\/p>\n

We visit the left subtree on node-9 and move on its own subtrees until we find the tree’s leaves.<\/p>\n

Output so far<\/strong>: <\/p>\n

When we reach node-2 there are no left and right subtrees so we print it<\/p>\n

Output so far<\/strong>: 2<\/p>\n

Same way with node-5<\/p>\n

Output so far<\/strong>: 2, 5<\/p>\n

We return to node-9 and since we’re done with its subtrees we print the value 9<\/p>\n

Output so far<\/strong>: 2, 5, 9<\/p>\n

Back to node-6. We haven’t yet visited its right subtree so on we go<\/p>\n

Output so far<\/strong>: 2, 5, 9<\/p>\n

Node-4 has no left subtree, so we visit its right-hand one. <\/p>\n

Output so far<\/strong>: 2, 5, 9<\/p>\n

We visit node-8’s left and right subtrees which are empty and then return to node-8 and print its value<\/p>\n

Output so far<\/strong>: 2, 5, 9, 8<\/p>\n

Now that we’re done with node-4’s subtrees we print its value<\/p>\n

Output so far<\/strong>: 2, 5, 9, 8, 4<\/p>\n

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

Output so far<\/strong>: 2, 5, 9, 8, 4, 6<\/p>\n

And that’s it. We’ve traversed the tree In a post-order fashion and have printed its nodes.<\/p>\n

The algorithm that achieves that in C++ is the following:<\/p>\n