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    

Here's our guided, illustrated walk-through.

How do I use this guide?

How We'll Begin Solving

The main challenge with traversing a BST in an inorder manner is keeping track of the ancestor. After all, at every node we visit, we will need to check if there is a node further on its left. This will need to continue until we reach a leaf node, i.e., node with no children as our starting point:

Once at a leaf node, we can start visiting the other nodes as per the traversal. We now understand the point of our two methods. isThereNextNode() has to be used to see if more nodes are yet to be visited in the traversal. It will be useful to stop the traversal if we have visited all of them. As long as there are more nodes to visit, nextNode() will have to keep track of them and visit them with each call.

One relatively naive approach is to use the stack data structure. Our constructor function can initialize the stack and keep track of the ancestors as it tries to find the leaf node to start with:

Then, we pop the stack and visit the node we get. We can check if the current node has a node to the right. If there is, we traverse it in an inorder way.

Have a look at the attached code that implements this approach.

xxxxxxxxxx

console.log('traversalObj.isThereNextNode()', traversalObj.isThereNextNode());

// 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)

}

​

class Stack {

​

  constructor()

  {

    this.items = [];

  }

​

    push(element)

    {

        this.items.push(element);

    }

​

    pop()

    {

        if (this.items.length == 0)

            return;

        return this.items.pop();

    }

​

}

​

​