Simple accepted Java code using stack and inorder traversal

  • -3

    The idea is to use a stack: first push all elements into the stack by inorder traversal, then pop each element out as the next() method is called.

    public class BSTIterator {
    Stack<Integer> treeStack;

    public BSTIterator(TreeNode root) {
        treeStack = new Stack<Integer>();
        if (root!=null)
            eulerTraversal(root); //Push elements into stack
    public void eulerTraversal(TreeNode v) {
        if (v.right!=null) {
            //Visit node v on the right
        //Visit v
        if (v.left!=null) {
            //Visit node v on the left
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !treeStack.isEmpty();
    /** @return the next smallest number */
    public int next() {
        return treeStack.pop();


  • 0

    O(h) memory?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.