fork download
copy 
  1. #include <iostream>
  2.  
  3. struct BST {
  4.     struct Node {
  5.         Node *left;
  6.         Node *right;
  7.         Node *parent;
  8.         int count;
  9.         int value;
  10.     };
  11.     Node *root;
  12.     BST() : root(0) {
  13.     }
  14.     void add(Node *parent, int value) {
  15.         if (parent) {
  16.             Node *node = new Node();
  17.             node->value = value;
  18.             node->left = 0;
  19.             node->right = 0;
  20.             node->parent = parent;
  21.             node->count = 1;
  22.             if (parent->left)
  23.                 parent->right = node;
  24.             else
  25.                 parent->left = node;
  26.             while (parent) {
  27.                 parent->count++;
  28.                 parent = parent->parent;
  29.             }
  30.         } else {
  31.             root = new Node;
  32.             root->count = 1;
  33.             root->parent = 0;
  34.             root->left = 0;
  35.             root->right = 0;
  36.             root->value = value;
  37.         }
  38.     }
  39.  
  40.     int countLessThan(const Node *n, int value) const {
  41.         if (n->value >= value) {
  42.             // The value has to be in the left sub-tree, so continue searching there:
  43.             if (n->left)
  44.                 return countLessThan(n->left, value);
  45.             else
  46.                 return 0;
  47.         } else {
  48.             // The value has to be in the right sub-tree, so continue searching there
  49.             // but include the whole left sub-tree and myself:
  50.             int count = 1;
  51.             if (n->left)
  52.                 count += n->left->count;
  53.             if (n->right)
  54.                 count += countLessThan(n->right, value);
  55.             return count;
  56.         }
  57.     }
  58.     int countLessThan(int value) {
  59.         return countLessThan(root, value);
  60.     }
  61. };
  62.  
  63. int main() {
  64.     // Create the BST as in the example:
  65.     BST *t = new BST;
  66.     t->add(NULL, 8);
  67.     t->add(t->root, 3);
  68.     t->add(t->root->left, 1);
  69.     t->add(t->root->left, 6);
  70.     t->add(t->root, 14);
  71.     t->add(t->root->right, 10);
  72.  
  73.     // Show some example outputs
  74.     for(int i = 0; i < 20; ++i) {
  75.         printf("countLessThan(%d) = %d\n", i, t->countLessThan(i));
  76.     }
  77. }
Success #stdin #stdout 0s 3028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
countLessThan(0) = 0
countLessThan(1) = 0
countLessThan(2) = 1
countLessThan(3) = 1
countLessThan(4) = 2
countLessThan(5) = 2
countLessThan(6) = 2
countLessThan(7) = 3
countLessThan(8) = 3
countLessThan(9) = 4
countLessThan(10) = 4
countLessThan(11) = 5
countLessThan(12) = 5
countLessThan(13) = 5
countLessThan(14) = 5
countLessThan(15) = 6
countLessThan(16) = 6
countLessThan(17) = 6
countLessThan(18) = 6
countLessThan(19) = 6
https://ideone.com/JcpjeK
language:
C++14 (gcc 8.3)
created:
11 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!