BadduCoder

SUBMITTED BY: BadduCoder

DATE: March 5, 2020, 5:09 p.m.

FORMAT: C++

SIZE: 1.5 kB

Raw Download

HITS: 521

Report
  1. // CPP program to find a pair with
  2. // given sum using hashing
  3. #include <bits/stdc++.h>
  4. using namespace std;
  6. struct Node {
  7. int data;
  8. struct Node *left, *right;
  9. };
  11. Node* NewNode(int data)
  12. {
  13. Node* temp = (Node*)malloc(sizeof(Node));
  14. temp->data = data;
  15. temp->left = NULL;
  16. temp->right = NULL;
  17. return temp;
  18. }
  20. Node* insert(Node* root, int key)
  21. {
  22. if (root == NULL)
  23. return NewNode(key);
  24. if (key < root->data)
  25. root->left = insert(root->left, key);
  26. else
  27. root->right = insert(root->right, key);
  28. return root;
  29. }
  31. bool findpairUtil(Node* root, int sum, unordered_set<int> &set)
  32. {
  33. if (root == NULL)
  34. return false;
  36. if (findpairUtil(root->left, sum, set))
  37. return true;
  39. if (set.find(sum - root->data) != set.end()) {
  40. cout << "Pair is found ("
  41. << sum - root->data << ", "
  42. << root->data << ")" << endl;
  43. return true;
  44. }
  45. else
  46. set.insert(root->data);
  48. return findpairUtil(root->right, sum, set);
  49. }
  51. void findPair(Node* root, int sum)
  52. {
  53. unordered_set<int> set;
  54. if (!findpairUtil(root, sum, set))
  55. cout << "Pairs do not exit" << endl;
  56. }
  58. // Driver code
  59. int main()
  60. {
  61. Node* root = NULL;
  62. root = insert(root, 15);
  63. root = insert(root, 10);
  64. root = insert(root, 20);
  65. root = insert(root, 8);
  66. root = insert(root, 12);
  67. root = insert(root, 16);
  68. root = insert(root, 25);
  69. root = insert(root, 10);
  71. int sum = 33;
  72. findPair(root, sum);
  74. return 0;
  75. }
comments powered by Disqus