Binary Tree Iterators

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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
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 nontrivial 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_{2}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.