Can anyone verify if this is O(1) time O(h) space solution?


  • 0
    H
    public class BSTIterator {
        Stack<TreeNode> stack;
    
        public BSTIterator(TreeNode root) {
            stack = new Stack<TreeNode>();
            addLeftNodes(root);
        }
        
        void  addLeftNodes(TreeNode node) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            } 
        }
    
        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty();
        }
    
        /** @return the next smallest number */
        public int next() {
            TreeNode next = stack.pop();
            // Add its right node's left nodes onto stack
            addLeftNodes(next.right);
            return next.val;
        }
    }

  • 2
    F

    Yes. Your next() runs in average O(1) time.
    The *next()*it is called n times, while in all the runtime of next(), each of the n nodes enters the stack at most 1 time (some nodes enter during construction) and leaves the stack exactly 1 time.

    And the space cost is O(h) time.
    The stack size grows only in addLeftNodes().
    Each time addLeftNodes() finishes, the node at top of the stack is a leaf.
    At the same time, right below each node is its parent or the parent of its parent.
    Thus, after addLeftNodes(), the node sequence in stack forms a (sometimes incompleted) path from root to a leaf. Such a path always has a length less than the height of the tree.


Log in to reply
 

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