One Pager Cheat Sheet

• Create a BSTInorderTraversal class that implements an iterator that traverses a binary search tree (BST) in an inorder fashion.
• Inorder traversal visits the nodes of a tree in the order left node, root, right node in a recursive manner.
• Candidates should understand the BST-based problem and use object-oriented programming to their advantage when solving it.
• We can use a naive stack approach to traverse a binary search tree (BST) in an inorder manner, starting from a leaf node and visiting each ancestor while checking if there is a node to the right.
• We can improve the efficiency of the traversal challenge by using the Morris Traversal approach, which uses recursion and stores references to nodes in the Node objects's attributes, to avoids using extra memory and reduce time complexity.
• The function recur will infinitely recur since each time it is called it subtracts 3 from its argument so the base case of num==1 is never reached.
• The space complexity of this approach is constant as values of variables are constantly reassigned.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

// 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 {TreeNode} rootNode

 */

​

var BSTInorderTraversal = function(rootNode) {

    this.currentNode = rootNode;

    this.rightMostNode = null;

};

​

/**

 * @return {number}

 */

BSTInorderTraversal.prototype.nextNode = function() {

    if (!this.isThereNextNode())

        return;

​

    if (this.currentNode.leftNode == null) {

        let temp = this.currentNode;

        this.currentNode = this.currentNode.rightNode;

        return temp.val;

    }

​

    this.rightMostNode = this.currentNode.leftNode;

​

    while (this.rightMostNode.rightNode != null

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.