Hierarchical Datastructure – Iterative Tree Traversals

Iterative approach for Postorder Traversal

As we already know the definition of postorder traversal, we will directly jump into the algorithm. The very first thing is to check if the node i.e. root is not null. If it is null then return from the method, because there is nothing to traverse. We will consider the same tree for traversal and below is the pseudo code:
postorderPseudoCode
We will require two Stacks S and O. We have the node reference which points to the root in the beginning. Push the node in the stack S, now we run an iteration till our stack S is not empty, in each iteration of the loop we pop the node from the stack and assign it to a temp node T and push it on the stack O. The Stack in green color is Stack O.

Evaluate if T has a left child, push it on the stack S and if the node T has a right child pushi it one the stack S. Please make a note of the order in which the children are pushed on the stack S. Repeat these steps till we have elements in the Stack S.

After the iteration is over, we need to have a look at the stack O. We pop everything from O one by one and print it.

Why do we do this?

Postorder traversal is to visit the left first, then the right and root node at the end. So first we push the root node and nodes having left or right in the O stack , as we know the O stack has to be accessed at the end. Lets understand this using a dry run.

Dry Run of the program

At this moment the S contains the ROOT.
st1_root
Iteration 1
S is not empty, pop ROOT from S and store it in T. Push ROOT on the stack O.
Check if T i.e. ROOT has a left child, yes it has left child P1. Push P1 on stack S.
Check if T i.e. ROOT has a right child, yes it has right child P3. Push P3 on stack S.
The stacks looks like below:
3st_1
Iteration 2
S is not empty, pop P3 from S and store it in T. Push P3 on the stack O.
Check if T i.e. P3 has a left child, yes it has left child C4. Push C4 on stack S.
Check if T i.e. P3 has a right child, yes it has right child C5. Push C5 on stack S.
The stacks looks like below:
3st_2
Iteration 3
S is not empty, pop C5 from S and store it in T. Push C5 on the stack O.
Check if T i.e. C5 has a left child, no it doesn’t have one.
Check if T i.e. C5 has a right child, no it doesn’t have one.
The stacks looks like below:
3st_3
Iteration 4
S is not empty, pop C4 from S and store it in T. Push C4 on the stack O.
Check if T i.e. C4 has a left child, no it doesn’t have one.
Check if T i.e. C4 has a right child, yes it has right child L5. Push L5 on stack S.
The stacks looks like below:
3st_4
Iteration 5
S is not empty, pop P1 from S and store it in T. Push P1 on the stack O.
Check if T i.e. P1 has a left child, yes it has left child C1. Push C1 on stack S.
Check if T i.e. P1 has a right child, yes it has right child C2. Push C2 on stack S.
The stacks looks like below:
3st_5
Iteration 6
S is not empty, pop C2 from S and store it in T. Push C2 on the stack O.
Check if T i.e. C2 has a left child, yes it has left child L2. Push L2 on stack S.
Check if T i.e. C2 has a right child, no it doesn’t have one.
The stacks looks like below:
3st_6
Iteration 7
S is not empty, pop L2 from S and store it in T. Push L2 on the stack O.
Check if T i.e. L2 has a left child, no it doesn’t have one.
Check if T i.e. L2 has a right child, no it doesn’t have one.
The stacks looks like below:
3st_7
Iteration 8
S is not empty, pop C1 from S and store it in T. Push C1 on the stack O.
Check if T i.e. C1 has a left child, yes it has left child L1. Push L1 on stack S.
Check if T i.e. C1 has a right child, no it doesn’t have one.
The stacks looks like below:
3st_8
Iteration 8
S is not empty, pop L1 from S and store it in T. Push L1 on the stack O.
Check if T i.e. L1 has a left child, no it doesn’t have one.
Check if T i.e. L1 has a right child, no it doesn’t have one.
The stacks looks like below:
3st_9
Now we don’t need another iteration because the Stack S is empty. Just pop elements one by one from O and print them in order.
3st_10
The final post order traversal result is L1, C1, L2, C2, P1, L5, C4, C5, P3, ROOT

Download the source

Here is the Github link for the sources used in this article.

Conclusion

In this article we learnt the iterative way of traversing tree. In the next article we will learn about the deleting a tree and more operations which can be done on the tree.

Hope this helps, happy reading. Stay connected and stay Subscribed