Tutorialspoint.dev

Find a pair with given sum in BST

Given a BST and a sum, find if there is a pair with given sum.

Input : sum = 28
        Root of below tree

Output : Pair is found (16, 12)



We have discussed different approaches to find a pair with given sum in below post.Find a pair with given sum in a Balanced BST

In this post, hashing based solution is discussed. We traverse binary search tree by inorder way and insert node’s value into a set. Also check for any node, difference between given sum and node’s value in set, if it is found then pair exists otherwise it doesn’t exist.

C++

// CPP program to find a pair with
// given sum using hashing
#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 findPair(Node* root, int sum)
{
    unordered_set<int> set;
    if (!findpairUtil(root, sum, set))
        cout << "Pairs do not exit" << endl;
}
  
// Driver code
int main()
{
    Node* root = NULL;
    root = insert(root, 15);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 8);
    root = insert(root, 12);
    root = insert(root, 16);
    root = insert(root, 25);
    root = insert(root, 10);
  
    int sum = 33;
    findPair(root, sum);
  
    return 0;
}

Python3

# Python3 program to find a pair with 
# given sum using hashing 
import sys
import math
  
class Node:
    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None
  
def insert(root,data):
    if root is None:
        return Node(data)
    if(data < root.data):
        root.left = insert(root.left, data)
    if(data > root.data):
        root.right = insert(root.right, data)
    return root
  
def findPairUtil(root, summ, unsorted_set):
    if root is None:
        return False
    if findPairUtil(root.left,summ,unsorted_set):
        return True
    if unsorted_set and (summ-root.data) in unsorted_set:
        print("Pair is Found ({},{})".format(summ-root.data, root.data))
        return True
    else:
        unsorted_set.add(root.data)
  
    return findPairUtil(root.right,summ, unsorted_set)
  
def findPair(root,summ):
    unsorted_set = set()
    if(not findPairUtil(root,summ,unsorted_set)):
        print("Pair do not exist!")
  
# Driver code
if __name__=='__main__':
    root=None
    root = insert(root,15)
    root = insert(root,10)
    root = insert(root,20)
    root = insert(root,8)
    root = insert(root,12)
    root = insert(root,16)
    root = insert(root,25)
    root = insert(root,10)
    summ = 33
    findPair(root, summ)
  
# This code is contributed by Vikash Kumar 37


Output:

Pair is found (8, 25)

Time Complexity is O(n).



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter