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