C++

Fill the Binary Search Tree with the values from the sample text file included in the email.

The code needs to be updated with the integers from this text file so I can search it later.

VIEW SAMPLE TEXT FILE HERE: https://drive.google.com/file/d/12wVXIrLM26bQZZU8Yk9gZZIa9QKyqb6s/view?usp=sharing

How much memory does your application occupy?

Attach Photo of Task Manager

How much time does it take to retrieve a node from the tree?

Run the lookup() method 3 times and measure in nanoseconds the time it takes.

#include

#include

using namespace std;

class BST { struct node { int data; node* left; node* right; };

node* root;

node* makeEmpty(node* t) { if(t == NULL) return NULL; { makeEmpty(t->left); makeEmpty(t->right); delete t; } return NULL; }

node* insert(int x, node* t) { if(t == NULL) { t = new node; t->data = x; t->left = t->right = NULL; } else if(x < t->data) t->left = insert(x, t->left); else if(x > t->data) t->right = insert(x, t->right); return t; }

node* findMin(node* t) { if(t == NULL) return NULL; else if(t->left == NULL) return t; else return findMin(t->left); }

node* findMax(node* t) { if(t == NULL) return NULL; else if(t->right == NULL) return t; else return findMax(t->right); }

node* remove(int x, node* t) { node* temp; if(t == NULL) return NULL; else if(x < t->data) t->left = remove(x, t->left); else if(x > t->data) t->right = remove(x, t->right); else if(t->left && t->right) { temp = findMin(t->right); t->data = temp->data; t->right = remove(t->data, t->right); } else { temp = t; if(t->left == NULL) t = t->right; else if(t->right == NULL) t = t->left; delete temp; }

return t; }

void inorder(node* t) { if(t == NULL) return; inorder(t->left); cout << t->data << " "; inorder(t->right); }

node* find(node* t, int x) { if(t == NULL) return NULL; else if(x < t->data) return find(t->left, x); else if(x > t->data) return find(t->right, x); else return t; }

public: BST() { root = NULL; }

~BST() { root = makeEmpty(root); }

void insert(int x) { root = insert(x, root); }

void remove(int x) { root = remove(x, root); }

void display() { inorder(root); cout << endl; }

void search(int x) { root = find(root, x); if(root == NULL) cout << x << " NOT FOUND!!" << endl; else cout << x << " FOUND" << endl; } };

int main() { BST t; t.insert(20); t.insert(25); t.insert(15); t.insert(10); t.insert(30); t.display(); clock_t t1,t2; t1 = clock(); t.search(20); t.search(10); t.search(40); t2 = clock(); double difference = (((float)t2)-((float)t1)); cout << "Time taken by lookup = " << difference * 1000000000; }