Post-order binary tree traversal is a technique used to visit all the nodes of a binary tree in the following order: First, all nodes in the left subtree of root node are visited in post-order fashion, then all the nodes in the right subtree of root node are visited in post-order fashion, and finally the root node of the current tree is visited. The animated examples discussed in the next section will make the definition more clear.
Animation of Post-Order Binary Tree Traversal
Let’s consider the below binary tree and apply the post-order tree traversal technique:
Node A is the root node of the binary tree. Before we visit this node, we need to visit all nodes under it’s left and right subtrees in post-order fashion. Visited nodes will be coloured in green.
First we need to visit all the nodes under the left subtree of node A i.e., subtree with root as node B in post-order fashion. We apply the post-order logic again i.e, first visit all nodes in left subtree under node B, then visit all nodes in right subtree under node B, and finally visit the subtree’s root node (B). Left subtree of node B contains a singe node D so we just visit that node, then visit node E and finally visit the subtree’s root node B,
Now that all the nodes under the left subtree of node A are visited, we need to visit all nodes under the right subtree of node A in post-order fashion.
Finally the root node can be visited.
This is the order in which we visited all the nodes: D, E, B, F, G, C, A.
Recursive Implementation
Below is the implementation of a function which takes in the root node of a binary tree and traverses all the nodes in Post-Order fashion. It uses recursion technique which is much simpler and straightforward than the iterative version.
Iterative Implementation