Question

• This assignment calls for generating a Binary Search Tree (BST) and scanning it in a preorder and a Breadth First Search (BFS) way.

• The program gets a parameter ? from the command line and stores ? randomly generated integers in a dynamic array. To generate a random integer between 1 and Max-Rand (a system constant):

▪ Use srand() to seed the rand() function. Then, call rand() again and again (? times) to generate ? random integers. Next, printout the values stored in the dynamic array.

• Next, the program stores the content of the array into a BST.

• Next, the program performs a preorder exploration of the BST and prints out the contents of the tree according to the pre-order exploration during visit.

• Finally, the program performs BFS on the BST and prints out the content of the tree according to the BFS visit order.

▪ You can use queue for the BFS.

Answer 1

Answer:

I have written the code based on your requirements.

The code is error-free and it is working perfectly.

I have also added the output-screenshot that I got by running the below program.

Output:

Enter an Integer : 10

Preorder :1458127707 687154677 433243266 218170988 810241110 797489018 1751937168 1480755986 1595744206 1533785652   

Breadth First Search :
1458127707 687154677 1751937168 433243266 810241110 1480755986 218170988 797489018 1595744206 1533785652

Code:

#include<bits/stdc++.h>
using namespace std;

struct Node
{
int data;
Node *left,*right;
};

Node *newnode(int data)
{
Node *temp=new Node();
temp->data=data;
temp->left=NULL;
temp->right=NULL;
  
return temp;
}

Node *insert(Node *root,int data)
{
if(root==NULL)
{
return newnode(data);
}
else
{
if(data < root->data)
{
root->left=insert(root->left,data);
}
else
{
root->right=insert(root->right,data);
}
  
return root;
}
}

void preorder(Node *root)
{
if(root!=NULL)
{
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}

void bfs(Node *root)
{
if(root==NULL)
return;
  
cout<<"\n\nBreadth First Search : \n";
  
queue<Node*> q;
  
q.push(root);
  
while(!q.empty())
{
  

  
Node * top=q.front();
q.pop();
  
cout<<top->data<<" ";
  
if(top->left)
{
q.push(top->left);
}
if(top->right)
{
q.push(top->right);
}
  
  
  
  
}
  
}
int main()
{
Node *root=NULL;
  
int n;
  
cout<<"Enter an Integer : ";
cin>>n;
  
int arr[n];
  
srand(time(0));
  
for(int i=0;i<n;i++)
{
arr[i]=rand()%RAND_MAX+1;
}
  
for(int i=0;i<n;i++)
{
root=insert(root,arr[i]);
}
  
  
cout<<"\n\nPreorder :";
preorder(root);
  
bfs(root);
  
}