Write an In-Order Iterator for a Binary Tree

Given a binary tree, write a method to implement an iterator that performs an in-order traversal of a binary tree.

Statement

Given a binary tree, write an iterator that takes in the root of a binary tree and iterates through its nodes in an in-order fashion.

Our implementation should include two critical methods of any iterator type:

  • hasNext(): This function returns whether an in-order node exists next in line.
  • getNext(): This function returns the next in-order node of the binary tree.

The method inorderUsingIterator in the “Try it yourself” section demonstrates how these two methods may be used to test our implementation.

Example

Consider the following binary tree:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.