Clean JavaScript O(n) time O(h) space solution


  • 0

    When we solve the problem in Binary Search Tree Iterator, we know that the next() should run in average O(1) time and use O(h) space, where h is the height of the tree. If we can have two iterators to help us fetch the next small and large values from the BST, we can easily solve this problem.

    const findTarget = (root, k) => {
        let i1 = new Iterator(root, false),
            i2 = new Iterator(root, true),
            left = i1.next(),
            right = i2.next();
        
        while (left < right) {
            const sum = left + right;
            
            if (sum === k) return true;
            
            if (sum < k)   left = i1.next();
            else           right = i2.next(); 
        }
        
        return false;
    };
    
    class Iterator {
        constructor(root, reverse) {
            this.stack = [];
            this.node = root;
            this.reverse = reverse;
        }
        
        next() {
            while (this.node) {
                this.stack.push(this.node);
                this.node = this.reverse ? this.node.right : this.node.left;
            }
    
            const current = this.stack.pop();
            this.node = this.reverse ? current.left : current.right;
            return current.val;
        }
    }
    

    Time complexity: O(n)
    Space complexity: O(h)


Log in to reply
 

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