Find a pair with given sum in BST in C++

In this tutorial, we are going to learn about how to Find a pair with a given sum in BST. Firstly we will have an introduction on BST. Secondly, we will discuss the logic. And Finally, Implement it using C++.

Introduction to BST and ways of traversal of tree

BST is a short form for Binary search tree. BST consist of nodes and edges. The nodes store data and edges are required to connect them. The nodes in BST has to be filled from left to right first. In BST one parent can only have two children maximum. Another rule that applies on BST is that the value of the left child has to be less than the parent. And the value of the right child has to larger than the parent.

to access the node we have to traverse the tree from the start node to the required node.

There are three methods of traversing:

  1. Preorder Traversal
  2. Postorder Traversal
  3. Inorder Traversal

In this tutorial, we are going to use Inorder Traversal. In Inorder Traversal we first check the parent then the left and then right node. We have to find two nodes which combine to give a sum of the required value.

We are also using hashing in this solution. Hashing makes the whole searching process much faster.

Program to find pair in BST

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node { 
    int data; 
    struct Node *left, *right; 
}; 
  
Node* NewNode(int data) 
{ 
    Node* temp = (Node*)malloc(sizeof(Node)); 
    temp->data = data; 
    temp->left = NULL; 
    temp->right = NULL; 
    return temp; 
} 
  
Node* insert(Node* root, int key) 
{ 
    if (root == NULL) 
        return NewNode(key); 
    if (key < root->data) 
        root->left = insert(root->left, key); 
    else
        root->right = insert(root->right, key); 
    return root; 
} 
  
bool findpairUtil(Node* root, int sum,  unordered_set<int> &set) 
{ 
    if (root == NULL) 
        return false; 
  
    if (findpairUtil(root->left, sum, set)) 
        return true; 
  
    if (set.find(sum - root->data) != set.end()) { 
        cout << "Pair is found ("
             << sum - root->data << ", "
             << root->data << ")" << endl; 
        return true; 
    } 
    else
        set.insert(root->data); 
  
    return findpairUtil(root->right, sum, set); 
} 
  
void pairfinder(Node* root, int sum) 
{ 
    unordered_set<int> set; 
    if (!findpairUtil(root, sum, set)) 
        cout << "Pairs do not exit" << endl; 
} 

int main() 
{
  int num,sum,data;
    Node* root = NULL; 
    cout<<"Enter the number of nodes : ";
    cin>>num;
    cout<<"Enter the data : ";
    for(int i=0;i<num;i++){
    	cin>>data;
    	root = insert(root, data);
  }
  cout<<"Enter the value of sum : ";
  cin>>sum;
    pairfinder(root, sum); 
  
    return 0; 
}

Input and Output : 

Enter the number of nodes: 5
Enter the data: 10
20
30
40
50
Enter the value of sum: 60
Pair is found (20, 40)

In the above code, we have Firstly taken the number of nodes. Secondly, we have taken the values of the nodes 0f the tree. Finally, the value of the sum is taken and the output is printed. This is the tutorial on Find a pair with given sum in BST in C++. Thank You for reading.

Conclusion

This solution can be used in many different problems. Hashing, trees and many important concepts are all included in this solution.

Also Checkout : 

Quick Sort in C++

BST implementation

Leave a Reply

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