### 653.Two Sum IV - Input is a BST

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

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

Example 3:

Input: root = [2,1,3], k = 4 Output: true

Example 4:

Input: root = [2,1,3], k = 1 Output: false

Example 5:

Input: root = [2,1,3], k = 3 Output: true

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`

Algorithm to solve the problem

We can do the following steps to solve the problem.- We can make a vector which is will be accessible to all the functions. Let it ve 'V'.
- We will make a helper function in which we will perform the following operations.
- We will store the values of each node of the BST in inorder traversal( Inorder traversal is a way of moving to every node in a tree in the order
- First the Root's left
- Then Root
- Then Root's right

- When we are doing Inorder traversal we will store the value of the node in our vector 'V'.
- If the root is NULL we will simply return.

- In our main function, we will first call our helper function so that every value gets stored in our vector.
- Now we will do the same thing as we use to do in the Two Sum Problem.
- We will make two pointers pointing to the start and the end of the vector.
- We will find the sum of the values at the start and the end, and then we will have three conditions based on the sum and the target value.
- If our sum is greater than the target, we will decrease the value of the end pointer.
- If our sum is smaller than the target then we will increase the value of the start pointer.
- If our sum equals we simply return true.

- This will run until end>start . Otherwise, we return false.
- Our algorithm is complete, now move to the code section.

The solution to the Above Question

- We can make a vector which is will be accessible to all the functions. Let it ve 'V'.
- We will make a helper function in which we will perform the following operations.
- We will store the values of each node of the BST in inorder traversal( Inorder traversal is a way of moving to every node in a tree in the order
- First the Root's left
- Then Root
- Then Root's right
- When we are doing Inorder traversal we will store the value of the node in our vector 'V'.
- If the root is NULL we will simply return.
- In our main function, we will first call our helper function so that every value gets stored in our vector.
- Now we will do the same thing as we use to do in the Two Sum Problem.
- We will make two pointers pointing to the start and the end of the vector.
- We will find the sum of the values at the start and the end, and then we will have three conditions based on the sum and the target value.
- If our sum is greater than the target, we will decrease the value of the end pointer.
- If our sum is smaller than the target then we will increase the value of the start pointer.
- If our sum equals we simply return true.
- This will run until end>start . Otherwise, we return false.
- Our algorithm is complete, now move to the code section.

**/**
* 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: vector<int>v;
void helper(TreeNode* root){
if(root==NULL){
return;
}
helper(root->left);
v.push_back(root->val);
helper(root->right);
}
bool findTarget(TreeNode* root, int k) {
helper(root);
int start=0;
int end=v.size()-1;
while(end>start){
if(v[start]+v[end]==k){
return true;
}
else if(v[start]+v[end]>k){
end--;
}
else{
start++;
}
}
return false;
}
};**

## 0 Comments

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.