1// Definition for a binary tree node.
2function TreeNode(val, leftNode, rightNode) {
3    this.val = (val===undefined ? 0 : val)
4    this.leftNode = (leftNode===undefined ? null : leftNode)
5    this.rightNode = (leftNode===undefined ? null : rightNode)
6}
7
8/**
9 * @param {TreeNode} rootNode
10 */
11
12var BSTInorderTraversal = function(rootNode) {
13    this.currentNode = rootNode;
14    this.rightMostNode = null;
15};
16
17/**
18 * @return {number}
19 */
20BSTInorderTraversal.prototype.nextNode = function() {
21    if (!this.isThereNextNode())
22        return;
23
24    if (this.currentNode.leftNode == null) {
25        let temp = this.currentNode;
26        this.currentNode = this.currentNode.rightNode;
27        return temp.val;
28    }
29
30    this.rightMostNode = this.currentNode.leftNode;
31
32    while (this.rightMostNode.rightNode != null
33            && this.rightMostNode.rightNode != this.currentNode)
34        this.rightMostNode = this.rightMostNode.rightNode;
35
36    if (this.rightMostNode.rightNode == null) {
37        this.rightMostNode.rightNode = this.currentNode;
38        this.currentNode = this.currentNode.leftNode;
39    }
40
41    else {
42        this.rightMostNode.rightNode = null;
43        let temp = this.currentNode;
44        this.currentNode = this.currentNode.rightNode;
45        return temp.val;
46    }
47
48    return this.nextNode();
49
50
51};
52
53/**
54 * @return {boolean}
55 */
56BSTInorderTraversal.prototype.isThereNextNode = function() {
57    return this.currentNode != null;
58};
59
60
61
62
63var assert = require('assert');
64
65try {
66
67    let root = new TreeNode(5);
68    root.leftNode = new TreeNode(3);
69    root.rightNode = new TreeNode(8);
70    root.rightNode.leftNode = new TreeNode(7);
71    root.rightNode.rightNode = new TreeNode(15);
72
73    const traversalObj = new BSTInorderTraversal(root);
74
75    assert(traversalObj.nextNode() == 3);
76    assert(traversalObj.isThereNextNode() == true);
77
78    console.log(
79        "PASSED: first call to traversalObj.nextNode() should get us 3 & first call to traversalObj.isThereNextNode() should get us True"
80    );
81
82} catch (err) {
83  console.log(err);
84}
85
86try {
87
88    let root = new TreeNode(15);
89    root.leftNode = new TreeNode(8);
90    root.rightNode = new TreeNode(25);
91    root.rightNode.leftNode = new TreeNode(20);
92
93    traversalObj = new BSTInorderTraversal(root);
94
95    assert([traversalObj.nextNode(), traversalObj.nextNode(), traversalObj.nextNode()], [8, 15, 25]);
96
97  console.log(
98            "PASSED: first three calls to traversalObj.nextNode() should get us 3, 15, and 25 respectively."
99  );
100
101} catch (err) {
102  console.log(err);
103}