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).
leave a comment
0 Comments