Good evening! Here's our prompt for today.

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:

1Node root = Node(5);
2root.left = new Node(3);
3root.right = new Node(8);
4root.right->left = new Node(7);
5root.right->right = new Node(15);
6
7BSTInorderTraversal traversalObj = new BSTInorderTraversal(root]);
8traversalObj.nextNode(); //should return 3
9traversalObj.isThereNextNode(); //should return true
10traversalObj.nextNode(); //should return 5
11traversalObj.nextNode(); //should return 7
12traversalObj.isThereNextNode(); //should return true
13traversalObj.nextNode(); //should return 8
14traversalObj.nextNode(); //should return 15
15traversalObj.isThereNextNode(); //should return false

Constraints

• The number of nodes in the BST that would get traversed is in the range [1,10⁵].
• 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.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

        "PASSED: first call to traversalObj.nextNode() should get us 3 & first call to traversalObj.isThereNextNode() should get us True"

// Definition for a binary tree node.

// function TreeNode(val, leftNode, rightNode) {

//     this.val = (val===undefined ? 0 : val)

//     this.leftNode = (leftNode===undefined ? null : leftNode)

//     this.rightNode = (leftNode===undefined ? null : rightNode)

// }

// /**

//  * @param {Node} rootNode

//  */

​

​

​

var BSTInorderTraversal = function(rootNode) {

    // write code here

};

​

/**

 * @return {number}

 */

BSTInorderTraversal.prototype.nextNode = function() {

    // write code here

};

​

/**

 * @return {boolean}

 */

BSTInorderTraversal.prototype.isThereNextNode = function() {

    // write code here    

We'll now take you through what you need to know.

How do I use this guide?