Question

In C++ with lots of comments please

Complete a binary search tree of 20 numbers

Show in the output the steps while it's performing the search with 20 numbers in a text file called list.txt

The numbers will be imported to the program

Simple program that should let you have the option to search for numbers, remove numbers, print numbers, and insert numbers in the binary tree

If the number isn't there then give an error

Answer 1

code in c++ (code to copy)

#include<bits/stdc++.h>
using namespace std;
class Node{
        public:
        int data;
        Node* left;
        Node* right;
        Node(int x):data(x){
                left=NULL;
                right=NULL;
        }
        //inserts an element in the tree
        static Node* insert(Node *root, int val){
                if(root==NULL)
                        return new Node(val);
                else{
                        if(val<root->data){
                                root->left=Node::insert(root->left, val);
                        }else{
                                root->right=Node::insert(root->right, val);
                        }
                }
        }
        //deletes the root of the tree
        static Node* popHead(Node *root){
                if(root==NULL){
                        cout<<"List is empty!"<<endl;
                        return NULL;
                }else{
                        Node* temp=root;
                        if(root->left==NULL){
                                root=root->right;
                        }else if(root->right==NULL){
                                root=root->left;
                        }else{
                                Node *r=root->right;
                                while(r->left!=NULL){
                                        r=r->left;
                                }
                                r->left=root->left;
                                root=root->right;
                        }
                        delete temp;
                        return root;
                }
        }
        //deletes an element in the tree
        static Node* deleteElement(Node* root, int ele){
                if(root==NULL){
                        cout<<"Number not found!"<<endl;
                        return NULL;
                }
                if(root->data==ele){
                        return Node::popHead(root);
                }else if(ele<root->data){
                        root->left = deleteElement(root->left, ele);
                }else{
                        root->right = deleteElement(root->right, ele);
                }
        }
        //searches for element in the binary search tree and prints the steps in a file
        static bool search(Node* root, int ele, ofstream &outfile){
                if(root==NULL){
                        //write step in file
                        outfile<<"Encountered null node, returning false!"<<endl;
                        return false;
                }
                if(root->data==ele){
                        outfile<<ele<<" = "<<root->data<<" : Found, returning true!"<<endl;
                        return true;
                }else if(ele<root->data){
                        outfile<<ele<<" < "<<root->data<<" : Searching in left sub tree!"<<endl;
                        return search(root->left, ele, outfile);
                }else{
                        outfile<<ele<<" > "<<root->data<<" : Searching in right sub tree!"<<endl;
                        return search(root->right, ele, outfile);
                }
        }
        // prints the tree in inorder
        static void print(Node* root){
                if(root==NULL)
                return;
                print(root->left);
                cout<<root->data<<" ";
                print(root->right);
        }
};
int main()
{
        //use ofstream to write search steps to file
        ofstream outfile("list.txt");
        int choice;
        //create a tree
        Node * root=NULL;
        while(true){
                cout<<"1. Add element"<<endl;
                cout<<"2. Search element"<<endl;
                cout<<"3. Remove element"<<endl;
                cout<<"4. Print Tree"<<endl;
                cout<<"5. Exit"<<endl;
                cin>>choice;
                switch(choice){
                        case 1: {
                                int ele;
                                cout<<"Enter element: ";
                                cin>>ele;
                                root=Node::insert(root, ele);
                        }break;
                        case 2: {
                                int ele;
                                cout<<"Enter element to search: ";
                                cin>>ele;
                                outfile<<"Searching for "<<ele<<endl;
                                cout<<"Search result: "<<(Node::search(root, ele, outfile) ? "found" : "not found")<<endl;
                                outfile<<endl;
                        }break;
                        case 3: {
                                int ele;
                                cout<<"Enter element to remove: ";
                                cin>>ele;
                                root = Node::deleteElement(root, ele);
                        }break;
                        case 4: {
                                cout<<"Printing tree: "<<endl;
                                Node::print(root);
                                cout<<endl;
                        }break;
                        default: exit(0);
                }
        }
}

code screenshot

Sample Input/Output screenshot

Contents of list.txt after execution