## Algorithm

Problem Name: 653. Two Sum IV - Input is a BST

Given the `root` of a binary search tree and an integer `k`, return `true` if there exist two elements in the BST such that their sum is equal to `k`, or `false` otherwise.

Example 1:

```Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
```

Example 2:

```Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
```

Constraints:

• The number of nodes in the tree is in the range `[1, 104]`.
• `-104 <= Node.val <= 104`
• `root` is guaranteed to be a valid binary search tree.
• `-105 <= k <= 105`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
unordered_map<int, int>m;
return DFS(root, m, k);
}

bool DFS(TreeNode* root, unordered_map < int, int>& m, int k){
if(!root) return false;
if(m.count(k - root->val)) return true;
m[root->val]++;
return DFS(root->left, m, k) || DFS(root->right, m, k);
}
};
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], k = 9

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
Stack < TreeNode> stack = new Stack<>();
Set set = new HashSet<>();
while (root != null) {
if (set.contains(k - root.val)) {
return true;
}
stack.push(root);
root = root.left;
}
while (!stack.isEmpty()) {
TreeNode removed = stack.pop();
TreeNode rightNode = removed.right;
while (rightNode != null) {
if (set.contains(k - rightNode.val)) {
return true;
}
stack.push(rightNode);
rightNode = rightNode.left;
}
}
return false;
}
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], k = 9

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findTarget = function(root, k) {
const m = new Map()
return traverse(root, k, m)
};

function traverse(node, k, m) {
if(node == null) return false
if(m.has(k - node.val)) return true
m.set(node.val, node)
return traverse(node.left,k,m) || traverse(node.right,k,m)
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], k = 28

Output

cmd
false

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
def traverse(node):
if not node: return False
if not node.val in dic: dic[k-node.val]=1
else: return True
return traverse(node.left) or traverse(node.right)
dic={}
return traverse(root)
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], k = 28

Output

cmd
false

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
//-----------------------------------------------------------------------------
// Runtime: 112ms
// Memory Usage: 30.1 MB
//-----------------------------------------------------------------------------

using System.Collections.Generic;

namespace LeetCode
{
/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
public class _0653_TwoSumIVInputIsABST
{
public bool FindTarget(TreeNode root, int k)
{
var set = new HashSet < int>();
return InOrder(root, k, set);
}

public bool InOrder(TreeNode node, int k, HashSet < int> set)
{
if (node == null) return false;
if (set.Contains(k - node.val)) return true;

return InOrder(node.left, k, set) || InOrder(node.right, k, set);
}
}
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], k = 9

Output

cmd
true