JavaScript solution using a Stack


  • 0
    E

    There are already several solutions shared here, but I don't often see someone sharing one written in JavaScript so I thought I'd share mine. The idea is the same is other solutions posted. We use a stack to keep track of subtree roots and when one is poped off in the next() call, we add all the left descendants of the targets right child. Adding only the left descendants allows us to achieving O(h) space complexity. It also allows us to achieve average O(1) time complexity since we will not always be traversing through the left descendants of the right child (Often times the target will have no right subtree). Simply checking if the stack is empty allows us to tell if there is another value for hasNext().

    JavaScript has a few syntactic sugars that makes writing this algorithm quite simple and elegant. I take advantage of objects 'truthy' values to make the code a little cleaner.

    var BSTIterator = function(root) {
        this.stack = [];
        while(root) {
            this.stack.push(root);
            root = root.left;
        }
    };
    
    BSTIterator.prototype.hasNext = function() {
        return this.stack.length != 0;
    };
    
    BSTIterator.prototype.next = function() {
        let subTreeRoot = this.stack.pop();
        let nextVal = subTreeRoot.val;
        
        subTreeRoot = subTreeRoot.right;
        while(subTreeRoot) {
            this.stack.push(subTreeRoot);
            subTreeRoot = subTreeRoot.left;
        }
        
        return nextVal;
    };
    

Log in to reply
 

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