• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



I would ask all the readers to give this chapter a special attention since if you have a strong grasp of the concept being introduced here, you would be able to think through and have an optimized O(n), where n is the total number of nodes present in the tree, solution for even a complex tree traversal problems in just few minutes.

We all know about the three types of DFS traversal in Binary Trees: Preorder, Inorder and Postorder. After reading this entire article, you will start appreciating the potential of the iterative implementations of Inorder Binary traversals as to how many different kinds of amazing and complex Binary Tree related problems you can solve so easily with them.
The reason for emphasizing on the iterative implementation is that we, in most cases, use recursive implementation of the Binary Tree DFS traversals to solve Binary Tree traversal problems, but I want to show how the iterative implementations of these traversals make our lives easier to solve problems. After you are done reading and assimilating this article you would have a whole different perspective on how to go about solving most Binary Tree related problems, and will make even some of the hardest Binary Tree problems seem easy.

Iterative Implementation:

Now that we know how the Binary Tree traversal works, let's look at the iterative algorithms for all of these traversals.

Inorder Traversal




Pay special attention to the following Iterative Inorder Traversal Implementation. This is one not as trivial as the other two iterative algorithm. Iterative inorder algorithm will come handy in solving many complex Tree problems.




Iterative Algorithm:

Let's revisit how inorder traversal works:
  • We traverse all the way to the left till the left-most node (i.e, the childNode of the with both childNodes as null)
    So we are looking at something like:
    
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
            
  • Once we are at the left most node, we process it.
            
                    // visit
                    root = stack.pop();
                    // process
                    res.add(root.val); //let's suppose we would just have to store it in an output list in inorder
                
    
  • Now that currentNode is processed visit its right childNode.
    root = root.right;
  • Repeat the above three steps as long as stack is non-empty or current node is not null
    
        while (!stack.isEmpty() || root != null) { // root is current Node here
        }
    
    
Now let's implement the algorithm:

Java code:


public List<Integer> inorderIterative(Node root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Deque<Node> stack = new ArrayDeque<>();
    while(!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        // visit
        root = stack.pop();
        // process
        res.add(root.val);

        root = root.right;
    }

    return res;
}



Python Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.







I prefer not to take Stack Java class. You almost never see a developer using Stack class in production level code. In production grade code you would see the use of Deque. Deque interface has all the methods you need to use it as a Stack or Queue as your need may be.

Remember one thing, what makes you stand out from the crowd in your coding interview is your ability to write Production Grade code. Make it your second nature. This may seem like a small thing, but it is not. It matters.





Applications of Iterative Inorder Traversal Algorithm:





Basically the challenge would be to first figure out if you need to do preorder, inorder or postorder traversal as part of your solution for a problem. Once you have figured that out, just try to think the traversal in the iterative way. After you have come up with the logic you need to implement for each visited node, simply write the iterative program, and put the logic after you are visiting the current node, where you are actually processing the node. It's that simple.



As you try to solve more and more tree traversal problems using iterative approach you would find that in most cases thinking in the iterative way feels much more natural, intuitive and easier.



Must Read Chapters:



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave