// // 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 */

BST.h file :

#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 data 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 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 data){ return search(root->left, value); } else { return search(root->right, value); } } }

#endif

example sample input : 100 should produce output : Found special number.

Instructions 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 N from 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. 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) Instructions 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 N from 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. 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)