Last active
August 29, 2015 14:20
-
-
Save HDegano/39d637eb184e902d9d7b to your computer and use it in GitHub Desktop.
Implement BSTIterator (Inorder)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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