fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. int l1, l2;
  5.  
  6. /* A binary tree Node has key, pointer to left and right children */
  7. struct Node
  8. {
  9.     int key;
  10.     struct Node* left, *right;
  11. };
  12.  
  13.  Node * parent1, *parent2;
  14.  
  15. /* Helper function that allocates a new Node with the
  16.    given key and NULL left and right pointers. */
  17. Node* newNode(int key)
  18. {
  19.     Node* temp = new Node;
  20.     temp->key = key;
  21.     temp->left = temp->right = NULL;
  22.     return (temp);
  23. }
  24.  
  25. void CalcSum(Node *node, int val1, int val2) 
  26. {  
  27.    queue <Node *> Q;
  28.  
  29.     Node *marker = new Node; // Marker node to indicate end of level
  30.  
  31.     int level = 1;   // Initialize level number
  32.  
  33.     // Enqueue the only first level node and marker node for end of level
  34.     Q.push(node);
  35.     Q.push(marker);
  36.  
  37.     // Simple level order traversal loop
  38.     while (Q.empty() == false)
  39.     {
  40.         // Remove the front item from queue
  41.         Node *n = Q.front();
  42.         Q.pop();
  43.  
  44.         if(node->left->key == val1 || node->right->key == val1)
  45.         {
  46.             parent1=node;
  47.             l1= level+1;
  48.         }
  49.  
  50.         if(node->left->key == val2 || node->right->key == val2)
  51.         {
  52.             parent2=node;
  53.             l2= level+1;
  54.         }
  55.         // Check if end of level is reached
  56.         if (n == marker)
  57.         {
  58.             // print a new line and increment level number
  59.             //cout << endl;
  60.             level++;
  61.  
  62.             // Check if marker node was last node in queue or
  63.             // level number is beyond the given upper limit
  64.             //if (Q.empty() == true || level > high) break;
  65.  
  66.             // Enqueue the marker for end of next level
  67.             Q.push(marker);
  68.  
  69.             // If this is marker, then we don't need print it
  70.             // and enqueue its children
  71.             continue;
  72.         }
  73.  
  74.         // If level is equal to or greater than given lower level,
  75.         // print it
  76.         //if (level >= low)
  77.             //cout << n->key << " ";
  78.  
  79.         // Enqueue children of non-marker node
  80.         if (n->left != NULL)  Q.push(n->left);
  81.         if (n->right != NULL) Q.push(n->right);
  82.     }
  83.     cout<<parent1<<" "<<parent2;
  84. }
  85.  
  86. /* Driver program to test above functions*/
  87. int main()
  88. {
  89.     // Let us construct the BST shown in the above figure
  90.     struct Node *root         = newNode(6);
  91.     root->left                = newNode(3);
  92.     root->right               = newNode(5);
  93.  
  94.     root->left->left          = newNode(7);
  95.     root->left->right         = newNode(8);
  96.     root->right->left         = newNode(1);
  97.     root->right->right        = newNode(3);
  98.  
  99.     //cout << "Level Order traversal between given two levels is";
  100.     CalcSum(root,3,5);
  101.     //cout<<sum;
  102.  
  103.     return 0;
  104. }
Time limit exceeded #stdin #stdout 5s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BOh5qz
language:
C++14 (clang 8.0)
created:
8 years ago
visibility:
public

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!