In this exercise, you will be working with Binary Search Trees to insert a large amount of numbers into a tree and then search for a specific element.Download and study the files BST.h, which contains an implementation of a Binary Search Tree along with the operations we have studied in class, and RandomSupport.h, which is just the library for generating random numbers that we have seen before.

Your task is to create a program that reads in a long value Nfrom the keyboard. Then create an empty Binary Search Tree and insert N random numbers into it. You are required to use the RandomSupport.h library to generate your random numbers, and they should all be positive (greater than 0).

Once the random numbers have been inserted, you need to call two functions. Assuming your Binary Search Tree is called root:

root = insertSpecialNumber(root);

and findSpecialNumber(root);The two functions above have been defined in a file called BSTUtil.h. Your program must include this file in order for all this to work. You are not given the file but you can assume it's in your working directory when you upload your .cpp file.Your program will be tested with input values on the order of millions of elements. Your program must be able to complete its work in a reasonable time (less than 5 seconds) for large inputs (~2 million elements).

BST_h

#ifndef BST_h #define BST_h struct Node { long data; Node* left; Node* right; }; void traverse(Node* root){ if (root != NULL){ traverse (root->left); std::cout << root->data << std::endl; traverse(root->right); } } Node* insert(Node* root, long value){ if (root == NULL){ root = new Node; root->data = value; root->left = NULL; root->right = NULL; } else{ if (value <= root->data){ root->left = insert(root->left, value); } else{ root->right = insert(root->right, value); } } return root; } bool search (Node* root, long value){ if (root == NULL){ return false; } else{ if (root->data == value){ return true; } else if (value < root->data){ return search(root->left, value); } else { return search(root->right, value); } } } #endif

--------------------------

RandomSupport_h

// // A small library for sampling random numbers from a uniform distribution // #ifndef RandomSupport_h #define RandomSupport_h #include  typedef std::uniform_int_distribution uniform_distribution; typedef std::mt19937 randomizer; randomizer new_randomizer(){ randomizer rng; rng.seed(std::random_device()()); return rng; } uniform_distribution new_distribution(long start, long end){ uniform_distribution dist(start, end); return dist; } long sample(uniform_distribution& dist, randomizer& r){ return dist(r); } #endif /* RandomSupport_h */