/*Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.*/

/**

* Definition for binary tree

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class BSTIterator {

public:

BSTIterator(TreeNode *root)

{

node = root;

nextItem = NULL;

}

/** @return whether we have a next smallest number */

bool hasNext()

{

pickNext();

return (nextItem != NULL);

}

/** @return the next smallest number */

int next()

{

return nextItem->val;

}

private:

// this var will b given to public API. will point to the current item in sequence

TreeNode *nextItem;

// these are system vars for inorder traversing

TreeNode *node;

list<TreeNode*> stack;

// use regular inorder traverse and stop if node is found.

void pickNext()

{

nextItem = NULL;

while (node != NULL || !stack.empty())

{

if (node != NULL)

{

stack.push_back(node);

node = node->left;

}

else

{

node = stack.back();

stack.pop_back();

// visit item

nextItem = node;

node = node->right;

// we found the node to visit. terminate the loop

break;

}

}

}

};

/**

* Your BSTIterator will be called like this:

* BSTIterator i = BSTIterator(root);

* while (i.hasNext()) cout << i.next();

*/