• 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.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Inorder Binary Tree Iterator:


Problem Statement: Write an Iterator (i.e. needs the next and hasNext methods if you are using Java) that takes the root of a binary tree and iterates through the nodes of the binary tree in Inorder fashion.

Solution:





  • Interesting Fact: All the problems discussed in this chapter often appear in homework assignments for Data Structures related classes in Harvard University. A simple web search would be enough to get the related links.


This chapter assumes that you have very good understanding of what an Iterator is. As we would see, the main challenge would be to implement the constructor and the next() method of the iterator. An easy way of thinking how to implement a Binary Tree Iterator would be to encapsulate the Iterative Tree Traversal into the next() method. So, we could keep a stack and make sure the next element is always on the top. This is exactly what we have implemented in the below code. If you have understood the thought process involved in the Iterative Inorder Traversal, you would have no hard time understanding the below code.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.





Preorder Binary Tree Iterator:

Problem Statement: Write an Iterator (i.e. needs the next and hasNext methods if you are using Java) that takes the root of a binary tree and iterates through the nodes of the binary tree in Preorder fashion.

Solution:

The thought process involved in implementing Iterative Preorder Traversal and the next() method of the iterator are the same.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.





Postorder Binary Tree Iterator:

Problem Statement: Write an Iterator (i.e. needs the next and hasNext methods if you are using Java) that takes the root of a binary tree and iterates through the nodes of the binary tree in Postorder fashion.

Solution:



Implementing Postorder Iterator is non-trivial and requires quite a bit of thinking. But if you have already done a good job at grabbing the thought process involved in Implementing Iterative Postorder Traversal using One Stack, then the below implementation would look very similar.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Space Complexity for all three iterators:


  • O(h), where h = height of the given binary tree = log2N , where N = total number of nodes in the given binary tree.


Use Cases:


We can use iterators to easily solve the below problem among many other use cases:
  • Determine if two given binary tree have same inorder / preorder / postorder traversal result.
    Solution: Take iterators for both binary trees and call the next() method for both iterators at the same time till the end of the iterators. If any point of time you get two different results from the next() call for the two iterators, the given binary trees do not yield same result for inorder / preorder / postorder traversal.


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