notes/OJ notes/pages/Leetcode Two-Sum-IV-Input-Is-a-BST.md

# Leetcode Two-Sum-IV-Input-Is-a-BST

#### 2022-07-08 11:11

> ##### Algorithms:
>
> #algorithm #binary_search #BFS
>
> ##### Data structures:
>
> #DS #binary_tree #binary_search_tree
>
> ##### Difficulty:
>
> #coding_problem #difficulty_easy
>
> ##### Additional tags:
>
> #leetcode
>
> ##### Revisions:
>
> N/A

##### Related topics:

##### Links:

- [Link to problem](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)
- [Three method to solve this](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106059/JavaC%2B%2B-Three-simple-methods-choose-one-you-like)

---

### Problem

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_.

#### Examples

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/09/21/sum_tree_1.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/09/21/sum_tree_2.jpg)

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

### Thoughts

> [!summary]
> This is a #BFS #hash_table problem.

Mainly two methods:

1. #BFS with hash table. Time space O(n)
   This can be quicker since you are starting at the middle, which is more likely to hit the answer, theoretically taking less time.
2. #binary_search. Time O(hn), h is the height of BST, best case h == log(n), worst case h == n
   for every node, binary search in the tree for the answer.

### Solution

BFS with hash table

```cpp
/**
 * Definition for a binary tree node.
 * 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 Solution {
public:
  bool findTarget(TreeNode* root, int k) {
    // BFS with unordered_set
    // Take note: when to push root, when to push root->left and root->right
    unordered_set<int> uset;
    queue<TreeNode*> pending;
    pending.push(root);

    TreeNode* ptr;
    while(!pending.empty()) {
      ptr = pending.front();
      pending.pop();

      // find first, to avoid k = 10, val = 5
      if (uset.find(ptr->val) != uset.end()) {
        return true;
      }
      uset.insert(k - ptr->val);

      if (ptr->left) {
        pending.push(ptr->left);
      }
      if (ptr->right) {
        pending.push(ptr->right);
      }
    }

    return false;
  }
};
```