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

# 653. Two Sum IV - Input is a BST

## Problem Statement

<br>

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

&#x20;

**Example 1:**

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

<pre><code><strong>Input: root = [5,3,6,2,4,null,7], k = 9
</strong><strong>Output: true
</strong></code></pre>

**Example 2:**

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

<pre><code><strong>Input: root = [5,3,6,2,4,null,7], k = 28
</strong><strong>Output: false
</strong></code></pre>

&#x20;

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

## Intuition

```
Approach:

Make an inorder and do Two sum
```

### Links

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

### Video Links

### Approach 1:

```
Two pointer
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int> arr;
    void inorder(TreeNode *root){
        if(root == nullptr)
            return ;

        inorder(root->left);
        arr.push_back(root->val);
        inorder(root->right);
    }

    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        int low=0, high=arr.size()-1;

        while(low<high){
            int sum = arr[low] + arr[high];
            if(sum == k)
                return true;
            else if(sum > k)
                high--;
            else
                low++;
        }

        return false;
    }
};
```

{% endcode %}

### Approach 2:

```
Hash - Two sum
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int> arr;
    void inorder(TreeNode *root){
        if(root == nullptr)
            return ;

        inorder(root->left);
        arr.push_back(root->val);
        inorder(root->right);
    }

    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        unordered_map<int,int> mp;

        for(auto &it: arr){
            if(mp.find(k-it) == mp.end())
                mp[it]++;
            else   
                return true;
        }

        return false;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###