# Two Sum IV - Input is a BST

Published: Dec 6, 2022

Easy Hash Table Breadth-First Search Tree Binary Search Tree

## Problem Description

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

Constraints:

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

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

## Examples

``````Example 1
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Explanation: (5, 4), (3, 6) and (2, 7)
5
/   \
3     6
/  \     \
2     4     7
``````
``````Example 2
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
Explanation: None of pair sums up to 28.
5
/   \
3     6
/  \     \
2     4     7
``````

## How to Solve

Although the given tree is the binary search tree (BST), its property doesn’t help to find the answer. A pair of two numbers can be found anywhere, not always from top to bottom. Because of this, every tree node should be checked like a binary tree.

The solution here uses the breadth-first search. While traversing the tree, (k - node value)s are saved in the set. If the current node’s value is in the set, the combination is found.

## Solution

``````/**
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class TwoSum4BST {
public:
bool findTarget(TreeNode* root, int k) {
if (!root) {
return false;
}
queue<TreeNode*> q({root});
set<int> seen;
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (seen.find(cur->val) != seen.end()) {
return true;
}
seen.insert(k - cur->val);
if (cur->left) {
q.push(cur->left);
}
if (cur->right) {
q.push(cur->right);
}
}
return false;
}
};
``````
``````
``````
``````
``````
``````# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class TwoSum4BST:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
if not root:
return False
seen, queue = set(), [root]
while queue:
cur = queue.pop(0)
if cur.val in seen:
return True
``````
• Time: `O(n)`
• Space: `O(n)`