Two Sum problem in a BST || C++ solution
Two Sum problem in a BST
In this problem, a BST and an integer (let k) is given. We have to tell whether we can get the number k by adding the values of BST elements or not.
Approach 1:
In this approach, we will go to every node and note its value. Now we will traverse the BST to find a value (say t) such that this value plus the noted value equals k. If we get this equal to k, then return true else return false.
NOTE: while searching for t, we will use the property of BST, i.e, if t>node->value then go right else go towards left.
Time Complexity:
In the worst case, we will be traversing the whole BST which takes, O(n)
and for searching: O(height) or O(h)
so overall time complexity: O(n*h)
Space Complexity:
O(1)
C++ Code:
class Solution {
public:
bool findTwoSum(TreeNode* root, int k) {
if(root==NULL)return 0;
TreeNode* node=root;
return search(node,root,k);
}
bool search(TreeNode* node, TreeNode* root,int k){
if(root==NULL)return 0;
int t=root->val;
if(srt(node,root,k-t))return 1;
return search(node,root->left,k) || search(node,root->right,k);
}
bool srt(TreeNode* node,TreeNode* root,int t){
if(node==NULL)return 0;
if(node->left){
if(node->left->val==t and node->left!=root)return 1;
}
if(node->right){
if(node->right->val==t and node->right!=root)return 1;
}
return t>node->val?srt(node->right,root,t):srt(node->left,root,t);
}
};Approach 2:
In this approach, we will store the values of BST in a vector. We will be using inorder traversal as we know that the inorder traversal of BST is always sorted.
Now we will check whether the sum of the first and last element of the vector equals k or not. If it is equal to k then return true else if the sum is greater than k, it means that we have to reduce the sum, and we know that the vector is sorted so if we shift the last index to last-1 then the sum will reduce and again compare. If the sum is lower than k, it means we have to increase the sum, we can increase it by incrementing the starting index.
If starting index becomes greater than or equal to the last index, then no two pairs are present which can generate k.
Time Complexity:
for inorder traversal: O(n)
for vector traversal: O(n)
overall : O(n)
Space Complexity:
for storing : O(n)
C++ Code:
class Solution {
public:
bool findTwoSum(TreeNode* root, int k) {
if(root==NULL)return 0;
vector<int>v;
inorder(root,v);
return search(v,k);
}
void inorder(TreeNode* root, vector<int>&v){
if(root==NULL)return ;
inorder(root->left,v);
v.push_back(root->val);
inorder(root->right,v);
}
bool search(vector<int>&v,int k){
int i=0, j=v.size()-1;
while(i<j){
if(v[i]+v[j]==k)return 1;
if(v[i]+v[j]>k)j--;
else i++;
}
return 0;
}
};
Comments
Post a Comment