# Two Sum IV - Input is a BST

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

## Analysis

https://leetcode.com/articles/two-sum-iv/

BFS + HashSet

1. Remove an element,pp, from the front of thequeuequeue.
2. Check if the elementk-pk−palready exists in thesetset. If so, return True.
3. Otherwise, add this element,ppto thesetset. Further, add the right and the left child nodes of the current node to the back of thequeuequeue.
4. Continue steps 1. to 3. till thequeuequeuebecomes empty.
5. Return false if thequeuequeuebecomes empty.

BST In-order Traversal + Two Pointers

## Solution

BFS + HashSet - Time: O(n), Space O(n)

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
Set<Integer> set = new HashSet();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (set.contains(k - node.val)) {
return true;
}
}
return false;
}
}
``````

BST inorder + Two Pointers

``````public class Solution {
public boolean findTarget(TreeNode root, int k) {
List < Integer > list = new ArrayList();
inorder(root, list);
int l = 0, r = list.size() - 1;
while (l < r) {
int sum = list.get(l) + list.get(r);
if (sum == k)
return true;
if (sum < k)
l++;
else
r--;
}
return false;
}
public void inorder(TreeNode root, List < Integer > list) {
if (root == null)
return;
inorder(root.left, list);
inorder(root.right, list);
}
}
``````

Recursive + HashSet

``````public class Solution {
public boolean findTarget(TreeNode root, int k) {
Set < Integer > set = new HashSet();
return find(root, k, set);
}
public boolean find(TreeNode root, int k, Set < Integer > set) {
if (root == null)
return false;
if (set.contains(k - root.val))
return true;