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.class BSTIterator { private: stack<TreeNode*> st; public: BSTIterator(TreeNode *root) { findLeft(root); } bool hasNext() { if (st.empty()) return false; return true; } int next() { TreeNode* top = st.top(); st.pop(); if (top->right != NULL) findLeft(top->right); return top->val; } void findLeft(TreeNode* root) { TreeNode* p = root; while (p != NULL) { st.push(p); p = p->left; } } };