#include <string>

#include <iostream>

using namespace std;

class EmployeeInfo

{

public:

int id;

string name;

};

struct node

{

EmployeeInfo info;

node *left;

node *right;

};

class btree

{

public:

btree();

~btree();

void insert(EmployeeInfo key);

node *search(int key);

void destroy_tree();

private:

void destroy_tree(node *leaf);

void insert(EmployeeInfo key, node *leaf);

node *search(int key, node *leaf);

node *root;

};

btree::btree()

{

root=NULL;

}

void btree::destroy_tree(node *leaf)

{

if(leaf!=NULL)

{

destroy_tree(leaf->left);

destroy_tree(leaf->right);

delete leaf;

}

}

void btree::insert(EmployeeInfo key, node *leaf)

{

if(key.id< leaf->info.id)

{

if(leaf->left!=NULL)

insert(key, leaf->left);

else

{

leaf->left=new node;

leaf->left->info=key;

leaf->left->left=NULL; //Sets the left child of the child node to null

leaf->left->right=NULL; //Sets the right child of the child node to null

}

}

else if(key.id>=leaf->info.id)

{

if(leaf->right!=NULL)

insert(key, leaf->right);

else

{

leaf->right=new node;

leaf->right->info=key;

leaf->right->left=NULL; //Sets the left child of the child node to null

leaf->right->right=NULL; //Sets the right child of the child node to null

}

}

}

node *btree::search(int key, node *leaf)

{

if(leaf!=NULL)

{

if(key==leaf->info.id)

return leaf;

if(key<leaf->info.id)

return search(key, leaf->left);

else

return search(key, leaf->right);

}

else return NULL;

}

node *btree::search(int key)

{

return search(key, root);

}

void btree::destroy_tree()

{

destroy_tree(root);

}

void btree::insert(EmployeeInfo key)

{

if(root!=NULL)

insert(key, root);

else

{

root=new node;

root->info=key;

root->left=NULL;

root->right=NULL;

}

}

int main()

{

EmployeeInfo info[8];

btree *bt = new btree();

info[0].id = 1021;

info[0].name = "John Williams";

info[1].id = 1057;

info[1].name = "Bill witherspoon";

info[2].id = 2487;

info[2].name = "Jennifer Twain";

info[3].id = 3769;

info[3].name = "Sophia Lancaster";

info[4].id = 1017;

info[4].name = "Debbie Reece";

info[5].id = 1275;

info[5].name = "George McMullan";

info[6].id = 1899;

info[6].name = "Ashley Smith";

info[7].id = 4218;

info[7].name = "Josh Plemmons";

int i;

for(i=0;i<8;i++)

{

bt->insert(info[i]);

}

int id;

cout<<"enter an ID number : ";

cin>>id;

if(bt->search(id)==NULL)

cout<<id<<" ID not found"<<endl;

else

cout<<id<<" ID found."<<endl<<"Employee name is : "<<(bt->search(id))->info.name;

return 1;

}