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.

public class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode> ();
//store each left node in the stack
//the smallest left node is put on the top of the stack
while (root != null) {
stack.push(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode node = stack.pop();
int ret = node.val;
//check if the current node has right child
if (node.right != null) {
//update the node
node = node.right;
//push all of its left child in the stack
while (node != null) {
stack.push(node);
node = node.left;
}
}
return ret;
}
}

### Like this:

Like Loading...

*Related*