🙏

জয়  শ্রী  রাম

🕉

---

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:

• Prerequisite: Powerful Approach of Iterative Inorder Traversal

• 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.



Login to Access Content

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:

• Prerequisite: Iterative Preorder Traversal

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



Login to Access Content

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:

• Prerequisite: Iterative Postorder Traversal using One Stack

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.



Login to Access Content

Space Complexity for all three iterators:

• O(h), where h = height of the given binary tree = log₂N , 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.

Instructor: