Find a pair in BST with given sum

Given a binary search tree, we have to find a pair in BST with given sum. For example consider below binary search tree.

Find a pair in BST with given sum

Suppose we have to find a pair whose sum equals to 130. So from the above binary search tree we have a got a pair 80 and 50 whose sum is 130.




Below is the program to find a pair in BST with given sum.

#include<iostream>

#include <unordered_set>

using namespace std;

struct Node{
    
    int data;
    struct Node * left;
    struct Node * right;
};

struct Node * newNode(int data)
{
    struct Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    
    return temp;
}

void insert(struct Node **root, int data)
{
    if(*root == NULL)
    {  *root = newNode(data);
        return;
    }  
    
    if((*root)->data > data)
       insert(&(*root)->left,data);
    else
      insert(&(*root)->right,data);
       
}

bool havePair(struct Node * root, int sum,  unordered_set<int> &set)
{
    if(root == NULL)
     return false;
     
    if(havePair(root->left,sum,set))
       return true;
       
    if(set.find(sum-root->data) != set.end()){
        cout<<"Pair is: "<<sum-root->data<<" and "<<root->data;
        return true;
    }
    else
      set.insert(root->data);
    
    if(havePair(root->right,sum,set))
      return true;
      
     return false;
}


void findPairInBST(struct Node *root, int sum){
    unordered_set<int> set;
    
     if(!havePair(root,sum,set))
       cout<<"There is no pair available !!";
}

void print(struct Node * root){
    if(root == NULL)
        return;
    
    cout<<root->data<<" "; print(root->left);
    print(root->right);
    
}

int main(){
    
    struct Node * root = NULL;
    
    insert(&root,60);
    insert(&root,45);
    insert(&root,80);
    insert(&root,20);
    insert(&root,50);
    insert(&root,95);
    
    cout<<"Preorder Traversal: ";
    print(root);
    int sum = 130;
    cout<<endl;
    findPairInBST(root,sum);
    
    return 0;
}

Output

Preorder Traversal: 60 45 20 50 80 95 
Pair is: 50 and 80

Leave a Reply

Your email address will not be published. Required fields are marked *