Here is the interview question prompt, presented for reference.

We know the binary search tree (BST) structure and the three ways to traverse it: inorder, preorder, and postorder. Now, let's create a class that takes a BST and can traverse it in an inorder fashion.

Prompt

Implement the BSTInorderTraversal class, whose each object acts as an iterator over the inorder traversal of a BST. The class will have a constructor and two methods to traverse a BST:

• BSTInorderTraversal (Node rootNode) initializes a class object. It takes a Node object called rootNode to traverse on. The iterating pointer should be initialized to some number lower than any element in the tree.
• int nextNode() moves to the next node in the traversal and returns the number at the node.
• boolean isThereNextNode() checks if there is a next node in the traversal to the right and returns True if there is and False if not.

Note how initializing the traversal pointer to a number lower than any element in the tree would ensure the first call to the nextNode() function returns the smallest element in the BST.

Once the class is created, you should be able to pass a BST and call the methods as the iterator would as it traverses.

Input: [[BSTInorderTraversal, ], 'nextNode', 'isThereNextNode', 'nextNode', 'nextNode', 'isThereNextNode', 'nextNode', 'nextNode', 'isThereNextNode'] //array of function calls

[[5,3,8,null,null,7,15],[],[],[],[],[],[],[],[]] //array of parameters

The first array represents all the function calls that will be made. The second array shows the parameters passed to each function in the respective order. See the Explanation section below.

Output: [null,3,5,7,8,15] // array of returned values

This array represents the values that will get returned in a particular order.

Explanation:

The object will be instantiated and the methods called in the following way: ``` Node root = Node(5); root.left = new Node(3); root.right = new Node(8); root.right->left = new Node(7); root.right->right = new Node(15);

BSTInorderTraversal traversalObj = new BSTInorderTraversal(root]); traversalObj.nextNode(); //should return 3 traversalObj.isThereNextNode(); //should return true traversalObj.nextNode(); //should return 5 traversalObj.nextNode(); //should return 7 traversalObj.isThereNextNode(); //should return true traversalObj.nextNode(); //should return 8 traversalObj.nextNode(); //should return 15 traversalObj.isThereNextNode(); //should return false ```

Constraints

• The number of nodes in the BST that would get traversed is in the range [1,105].
• 0 <= Node.val <= 106
• The isThereNextNode, and nextNode will get called at most 105 times.
  

Before moving on to the solution, try out solving the problem yourself below. The window shows how the Node class is defined.

You can see the full challenge with visuals at this link.