Very neat 6ms Java Solution using Stack (but can anyone help analyse the complexity?)


  • 0
    public class BSTIterator {
        
        private Stack<TreeNode> path = new Stack<TreeNode>();
    
        public BSTIterator(TreeNode root) {
            while(root!=null) {
                path.push(root);
                root = root.left;
            }
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !path.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            TreeNode node = path.pop();
            if(node.right!=null) {
                TreeNode curr = node.right;
                while(curr!=null) {
                    path.push(curr);
                    curr = curr.left;
                }
            }
            return node.val;
        }
    }

  • 0

    i m weak at amortized complexity, what I observe is each time call next(), it searches down for smallest in right sub-tree(if any) and pushes all the nodes along the pah


  • 0
    C

    This is an interesting approach. But doesn't it violate the conditions that next() run in constant time?


  • 0
    D

    public class BSTIterator {
    private ArrayList<Integer> list = new ArrayList<Integer>();
    private int current = 0;
    public BSTIterator(TreeNode root) {
    inorder(root);
    }

    private void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(current < list.size())
            return true;
        else return false;
    }
    

    strong text

    /** @return the next smallest number */
    public int next() {
        return list.get(current++);
    }
    

    }

    Blockquote


  • 0
    A

    This is O(n) space, not O(h) space as specified in the problem.


  • 0
    D

    Thank you for your opinion,I don't have a close reading.


  • 3

    I did exactly the same solution (well, it's the class iterative algorithm), only moved that while loop into a separate helper method.

    I believe that the complexity is all right. Space-wise it's obvious because the maximum stack size is bounded by exactly the height of the tree.

    Time-wise it's a bit more tricky, but let's take a closer look. If we don't enter that while loop, then next() is instant. That's OK. If we enter the loop and suppose it runs for M iterations. This may look not very good, but on each iteration we push an element to the stack, right? And these elements are always used by later next() calls. That means the sum of those Ms is equal to the total number of elements in the tree, say, N. But then the total number of calls to next() is also N, so when we divide those summed extra costs by N we get average of 1 per one call. This is no big surprise since the number of "pushes" is equal to the number of "pops". So the average complexity is one push and one pop per call.


  • 0
    A

    Great analysis!


Log in to reply
 

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