Skip to content

Instantly share code, notes, and snippets.

@HDegano
Last active August 29, 2015 14:20
Show Gist options
  • Save HDegano/39d637eb184e902d9d7b to your computer and use it in GitHub Desktop.
Save HDegano/39d637eb184e902d9d7b to your computer and use it in GitHub Desktop.
Implement BSTIterator (Inorder)
/*
We need to build up on Inorder iterative
We can use a queue but that would take O(n) space
we can instead only push when we need to and only take up O(lgh), h is height
*/
public class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<TreeNode>();
TreeNode current = root;
while(current != null){
stack.push(current);
current = current.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
TreeNode top = stack.pop();
if(top.right != null){
TreeNode current = top.right;
while(current != null){
stack.push(current);
current = current.left;
}
}
return top.val;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment