Without Stack, beats 97.7% Java submission


  • 0
    A
    public class BSTIterator {    
        TreeNode bst;
        int size ; //Keep track of nodes that are fetched
        int num ; //Store the number of nodes
        List<Integer> inorder; //Inorder traversal of a BST
    
        public BSTIterator(TreeNode root) {
            bst = root;
            num =0;
            size=0;
            inorder = new ArrayList<>();
            traverse(root);
            
        }
        
        public void traverse(TreeNode root){
            if(root==null)
            return;
        
            traverse(root.left);
            inorder.add(root.val);
            num++;
            traverse(root.right);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            if(size<num) return true;
            return false;
            
        }
    
        /** @return the next smallest number */
        public int next() {
            return inorder.get(size++);
        }
    }
    

  • 0
    B

    This solution doesn't meet O(h) space criteria. You are using O(n) space, basically storing the whole tree in flat form and then iterating. People have used stack for O(h) reason.


Log in to reply
 

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