My Solution with less than 10 lines of code


  • 25
    H

    public class BSTIterator {

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

    }

    /**

    • Your BSTIterator will be called like this:
    • BSTIterator i = new BSTIterator(root);
    • while (i.hasNext()) v[f()] = i.next();
      */

  • 1
    I

    How do you prove that the amortized running time is constant?


  • 0

    @ivtoskov I'd say (anecdotally) that this is standard in order traversal, which visits each node once so over the course of requesting each node you'd get an average of all visits divided by all nodes which works out to O(1). Not sure that is proof but conceptually I think it is correct.


Log in to reply
 

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