fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Data structure to store a Binary Search Tree node
  5. struct Node {
  6.     int data;
  7.     Node *left, *right;
  8. };
  9.  
  10. // Function to create a new binary tree node having given key
  11. Node* newNode(int key)
  12. {
  13.     Node* node = new Node;
  14.     node->data = key;
  15.     node->left = node->right = nullptr;
  16.  
  17.     return node;
  18. }
  19.  
  20. // Function to find Minimum value node in subtree rooted at node
  21. int MinValue(Node* node)
  22. {
  23.     while (node->left)
  24.         node = node->left;
  25.  
  26.     return node->data;
  27. }
  28.  
  29. // Function to find Maximum value node in subtree rooted at node
  30. int MaxValue(Node* node)
  31. {
  32.     while (node->right)
  33.         node = node->right;
  34.  
  35.     return node->data;
  36. }
  37.  
  38. // Recursive function to insert an key into BST
  39. Node* insert(Node* root, int key)
  40. {
  41.     // if the root is null, create a new node an return it
  42.     if (root == nullptr)
  43.         return newNode(key);
  44.  
  45.     // if given key is less than the root node, recurse for left subtree
  46.     if (key < root->data)
  47.         root->left = insert(root->left, key);
  48.  
  49.     // if given key is more than the root node, recurse for right subtree
  50.     else
  51.         root->right = insert(root->right, key);
  52.  
  53.     return root;
  54. }
  55.  
  56. // Function to find a pair with given sum in given BST
  57. bool findPair(Node* X, Node* Y, int pair_sum, int x, int y)
  58. {
  59.     if (X == nullptr || Y == nullptr)
  60.         return false;
  61.  
  62.     // if current sum is less than the required sum, update x
  63.     if (x + y < pair_sum)
  64.     {
  65.         if (findPair(X->left, Y, pair_sum, x, y))
  66.             return true;
  67.  
  68.         x = X->data;
  69.  
  70.         // if current sum is equal to the required sum, 
  71.         // print the pair and return true
  72.         if (x + y == pair_sum)
  73.         {
  74.             cout << "Pair found (" << x << ", " << y << ")";
  75.             return true;
  76.         }
  77.  
  78.         return findPair(X->right, Y, pair_sum, x, y);
  79.     }
  80.  
  81.     // if current sum is more than the required sum, update y
  82.     else if (x + y > pair_sum)
  83.     {
  84.         if (findPair(X, Y->right, pair_sum, x, y))
  85.             return true;
  86.  
  87.         y = Y->data;
  88.  
  89.         // if current sum is equal to the required sum, 
  90.         // print the pair and return true
  91.         if (x + y == pair_sum)
  92.         {
  93.             cout << "Pair found (" << x << ", " << y << ")";
  94.             return true;
  95.         }
  96.  
  97.         return findPair(X, Y->left, pair_sum, x, y);
  98.     }
  99. }
  100.  
  101. // main function
  102. int main()
  103. {
  104.     int keys[] = { 7, 10, 9, 20 };
  105.  
  106.     Node* root = nullptr;
  107.     for (int key : keys)
  108.         root = insert(root, key);
  109.  
  110.     // given pair_sum
  111.     int pair_sum = 40;
  112.  
  113.     // find Minimum and Maximum key in binary search tree
  114.     int x = MinValue(root);
  115.     int y = MaxValue(root);
  116.  
  117.     if (!findPair(root, root, pair_sum, x, y))
  118.         cout << "Pair do not exists";
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Pair found (20, 20)
https://ideone.com/8qqGP8
Find a pair with given sum in a BST
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!