Binary tree traversals are generally done in a recursive manner because this type of problem tends to be simplified by such methods. Nevertheless, the key advantage gained by using an iterative approach is the fact that the traversal will not run out of stack space. Moreover, there is always something to learn when solving a problem in an alternative way.

Below are the iterative implementations of the different types of traversals that can be done with a binary tree alongside an explanation of how they work:

Pre-Order Traversal

Pre-Order traversal consists of traversing the left subtree before advancing to the right subtree. This behavior is achieved through the use of a Last In First Out (LIFO) data structure like a stack. The insertion of the right nodes occurs before the left nodes in order to make sure that the left nodes will be the first ones to be accessed.

Post-Order Traversal

The Post-Order iterative tree traversal algorithm is slightly more complex than the Pre-Order one because the solution uses two stacks. The first stack gets the reverse Post-Order traversal in a similar manner to the algorithm used for the Pre-Order traversal with the only difference that the left node is inserted before the right one. The purpose of the second stack is to get the reverse of the first stack and in turn get the proper Post-Order traversal.

In-Order Traversal

In-Order traversal involves a current pointer pivot that will traverse the leftmost part of the tree and insert itself to a stack until it reaches a null value. If the current pointer is null and the stack is not empty then the pivot pointer moves towards the rightward node from the node at the top of the stack, otherwise, the traversal stops as the whole tree has been accessed.

Level-Order Traversal

The Level-Order traversal algorithm is different from all the previous methods mentioned in the fact that it uses a First In First Out (FIFO) data structure in the form of a queue. The way it works consists of accessing every node in a single level and then insert the left and right child nodes to use them in the next cycle of iteration for each upcoming level. As a side note, it is not necessary to include the for loop to iterate through every level of the tree as the queue itself will handle this behavior; nevertheless, this is added to make a distinction for every level of the tree that is being accessed.

Conclusion

Undoubtedly, the iterative approach of traversing a binary tree traversal is a more verbose and complex solution when compared to its recursive counterpart. Despite that, implementing another way of traversing a tree adds a level of comprehension for key data structures such as stacks and queues, as well as, include the benefit of not having to worry about running out of stack space.

Source Code