My Accepted Java Solution: Did I miss something?


  • 0
    K

    here is my accepted java solution. I noticed in the accepted solution stats that it runs very quickly and seems shorter than a lot of other solutions here. I know that it was accepted, but am I missing some corner cases in this code?

       public class BSTIterator {
    
        private Stack<Integer> stack;
    
        public BSTIterator(TreeNode root) {
            stack = new Stack<Integer>();
            buildStack(root);
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return (!stack.empty());
        }
    
        /** @return the next smallest number */
        public int next() {
            return stack.pop();
        }
        
        private void buildStack(TreeNode node){
            if (node == null) return;
            buildStack(node.right);
            stack.push(node.val);
            buildStack(node.left);
        }
        
    }

  • 2
    C

    This is OK for corner case, but actually you are using o(N) space, since you pushed all the nodes to the stack. However, the question asks for a o(h) extra space solution, h is the height of the tree. Consider a height balanced BST, your solution needs more space.


  • 1
    D

    Your code works fine for corner cases. However, your solution needs O(n) space since you decide to traverse the tree once the root of the BST is given. The correct way to solve this problem in O(logn) space complexity is to simulate the traverse using stack instead of storing the inorder sequence beforehand.


  • 0
    K

    The question asks for O(1) runtime and O(h) memory for those two specific functions. This implementation runs them both in O(1) memory and O(1) space.


Log in to reply
 

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