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

• 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)`

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