My solutions in 3 languages with Stack


  • 282

    I use Stack to store directed left children from root.
    When next() be called, I just pop one element and process its right child as new root.
    The code is pretty straightforward.

    So this can satisfy O(h) memory, hasNext() in O(1) time,
    But next() is O(h) time.

    I can't find a solution that can satisfy both next() in O(1) time, space in O(h).

    Java:

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

    C++:

    class BSTIterator {
        stack<TreeNode *> myStack;
    public:
        BSTIterator(TreeNode *root) {
            pushAll(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !myStack.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode *tmpNode = myStack.top();
            myStack.pop();
            pushAll(tmpNode->right);
            return tmpNode->val;
        }
    
    private:
        void pushAll(TreeNode *node) {
            for (; node != NULL; myStack.push(node), node = node->left);
        }
    };
    

    Python:

    class BSTIterator:
        # @param root, a binary search tree's root node
        def __init__(self, root):
            self.stack = list()
            self.pushAll(root)
    
        # @return a boolean, whether we have a next smallest number
        def hasNext(self):
            return self.stack
    
        # @return an integer, the next smallest number
        def next(self):
            tmpNode = self.stack.pop()
            self.pushAll(tmpNode.right)
            return tmpNode.val
            
        def pushAll(self, node):
            while node is not None:
                self.stack.append(node)
                node = node.left

  • 15
    M

    I think you have the optimal solution. The question said "in average" O(1) time, which means amortized over all the next() calls.


  • 0

    nice solution!


  • 1
    S

    Your next() is amortized O(1) time. Nice one.


  • 5
    C

    Nice solution. It is actually breaks in-order traversal into hasNext() and next()


  • 4
    K

    This is really fantastic! It's better to replace class Stack<E> with interface Deque<E> and class LinkedList<E> in Java version.


  • 1
    Z

    Hi, xcv! Could you please explain more about the next function in Python? I really don't get it... Thanks so much!!


  • 0

    I don't understand which point you can't get. Can you explain what you think it does?


  • 4
    L

    Good solution ~~

    I have a question ..

    this problem said ::
    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    are these code here meet this requirement ?


  • 1

    As I mentioned above:
    "I can't find a solution that can satisfy both next() in O(1) time, space in O(h)."


  • 2
    S

    Your solution is indeed average O(1) time and O(h) space.

    Each node will be visited at most twice-> average O(1) run time.

    The stack will store at most h nodes -> O(h) space.


  • 36
    C

    The average time complexity of next() function is O(1) indeed in your case. As the next function can be called n times at most, and the number of right nodes in self.pushAll(tmpNode.right) function is maximal n in a tree which has n nodes, so the amortized time complexity is O(1).


  • 0
    L

    nice explanation


  • 0
    E

    Exactly the same with you.
    : )


  • 0
    L

    Chile, this code is beautiful


  • 0
    Z

    what's the next smallest number means? For example we have number [4,2,null,1,3], is the next smallest number 3?


  • 0

    It depends where you are.


  • 0
    S

    'return self.stack' in python's solution can really return a boolean value?


  • 0

    No and yes. return self.stack just return the stack itself. But if you treat the return value as boolean value, it does work.


  • 0
    T

    @siyang3 Are you sure? Because the problem states where H is the height of the tree and the height of the tree is log N where N is the number of nodes in the tree.


Log in to reply
 

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