> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/two-sum-iv.md).

# Two Sum IV

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

**Example 1:**

```
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True
```

**Example 2:**

```
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False
```

```java
class Solution {
    // O(N) Time & O(H) Space
    public boolean findTarget(TreeNode root, int k) {
        Deque<TreeNode> stackL = new LinkedList<TreeNode>(); // iterator 1 that gets next smallest value
        Deque<TreeNode> stackR = new LinkedList<TreeNode>(); // iterator 2 that gets next largest value
        for (TreeNode cur = root; cur != null; cur = cur.left)
            stackL.push(cur);
        for (TreeNode cur = root; cur != null; cur = cur.right)
            stackR.push(cur);
        while (stackL.size() != 0 && stackR.size() != 0 && stackL.peek() != stackR.peek()) {
            int tmpSum = stackL.peek().val + stackR.peek().val;
            if (tmpSum == k)
                return true;
            else if (tmpSum < k)
                for (TreeNode cur = stackL.pop().right; cur != null; cur = cur.left)
                    stackL.push(cur);
            else
                for (TreeNode cur = stackR.pop().left; cur != null; cur = cur.right)
                    stackR.push(cur);
        }
        return false;
    }
}
```