DFS (Deepth First Search) and BFS (Breadth First Search) are two approaches to traverse tree. It is relatively easy to implement BFS in an iterative manner (with the help of queue). While it is a bit challenging to do DFS without reursion.

Recursive DFS

There are three orders of DFS:

• Pre-order: means parent first, then left child, finally right child;
• In-order: means left child first, then parent, finally right child;
• Post-order: means left child first, then right child, finally parent;

With recursion, those three could be easily implemented at once:

However, recursion doesn’t use stack efficiently, and introduces overhead by plenty of recursive calls.

Pre-order Iterative DFS

In-order Interative DFS

Post-order Interative DFS

Credits

• GeeksforGeeks - Thanks for offering a platform where I can see others’ solutions and test my code.