Question

C++ Vectors and Binary Search Trees • Write a program that takes from the user n integers and stores them a vector of int. Then, create a function insert After that takes first Value and second Value. This function searches for each occurrence of first Value in the vector and insert the second Value after it in the same vector. The first and second values are taken from the user. • Create another function that creates a Binary Search Tree based on the vector's elements given that if the value occurs more than once in the vector then it should be reflected in the number of occurrences of that node in the Binary Search Tree. Write a function that would return O O if two binary search trees are identical (has the same nodes with the same values). If not identical, then the function returns . 1 if the sum of the values of the first tree is bigger than the second tree, . 2, if the sum of the values of both trees are equal, and . -1 if the sum of the values of the first tree is smaller than the second tree. Test this function based on a Binary Search Tree that contains double numbers • Delivery Guidelines: Please make sure that you documented your code

Answer 1

1. The requested code is below:-

//----------------------------------------------------------------------------------------

#include <iostream>
#include <vector>

using namespace std;

void input(vector<int> &nums)
{
   int n=0,num=0;
   cout<<"Enter Limit: ";
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cout<<"Enter an Integer: ";
       cin>>num;
       nums.push_back(num);
   }
}

void display(vector<int> nums)
{
   for(int x: nums)
   {
       cout<<x<<" ";
   }
   cout<<endl;
}

void insertAfter(vector<int> &nums,int firstValue,int secondValue)
{
   int i=0;
   for(int num: nums)
   {
       i++;
       if(num==firstValue)
           break;
   }
   nums.insert(nums.begin()+i,secondValue);
}

// BST node
struct Node
{
int data;
struct Node* left;
struct Node* right;
};

typedef struct Node Node;

// Utility function to create a new Node
Node* createNode(int data)
{
Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
  
return node;
}

Node* insert(Node* node,int data)
{
   if(node == NULL)
       return createNode(data);
   if (data <= node->data)
       node->left = insert(node->left, data);
   else if (data > node->data)
       node->right = insert(node->right, data);
   return node;
}
  
// Function to perform inorder traversal
void inorder(Node* root)
{
if (root == NULL)
       return;
  
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
  
// Function to check if two BSTs
// are identical
int isIdentical(Node* root1, Node* root2)
{
// Check if both the trees are empty
if (root1 == NULL && root2 == NULL)
return 1;
// If any one of the tree is non-empty
// and other is empty, return false
else if (root1 != NULL && root2 == NULL)
return 0;
else if (root1 == NULL && root2 != NULL)
return 0;
else
   { // Check if current data of both trees equal
// and recursively check for left and right subtrees
if (root1->data == root2->data && isIdentical(root1->left, root2->left) && isIdentical(root1->right, root2->right))
return 1;
else
return 0;
}
}

Node* buildTree(Node *root,vector<int> nums)
{
   for(int x: nums)
   {
       root=insert(root,x);
   }
   return root;
}

int sum(Node*root)
{
   if (root == NULL)
return 0;
else
       return (root->data + sum(root->left) + sum(root->right));
}

int compareTree(Node* root1, Node* root2)
{
   if(isIdentical(root1,root2))
   { // if both trees are same return zero
       return 0;
   }
   else
   {
       int sum1=sum(root1); // sum of first tree
       int sum2=sum(root2); // sum of second tree
       if(sum1>sum2)
       {
           return 1;
       }
       else if(sum1<sum2)
       {
           return -1;
       }
       else // sum1 == sum2
       {
           return 2;
       }
   }
}

int main(int argc,char**argv)
{
   int cmp=0;
   Node *root1=NULL;
   Node *root2=NULL;
   // Part 1 :-
   vector<int> nums(0);
   input(nums);
   insertAfter(nums,6,5);
   cout<<"Vector of Integers:-"<<endl;
   display(nums);
   // Part 2 :-
   root1 = buildTree(root1,nums);
   cout<<"Binary Tree 1 :-"<<endl;
   inorder(root1);
   cout<<endl;
   root2 = insert(root2,9);
   root2 = insert(root2,8);
   root2 = insert(root2,7);
   root2 = insert(root2,6);
   root2 = insert(root2,5);
   cout<<"Binary Tree 2 :-"<<endl;
   inorder(root2);
   cout<<endl;
   cmp = compareTree(root1,root2);
   cout<<"Result = "<<cmp<<endl;
   return 0;
}

//----------------------------------------------------------------------------------------

2.Screenshot of the output:-

- o + 7 C:\Users\vipul\Documents\SourceCode\HighLvl\data_structures.cpp - Notepad++ File Edit Search View Encoding Language Settings Tools Macro Run Plugins Window ? + M N N N D N N 0 N 0 N 0 1 data_structures.cpp X // Part 1 :- vector int> nums (0) ; input (nums); insertAfter (nums , 6,5); cout<<"Vector of Integers:-"<<endl; display (nums); // Part 2 :- rootl = buildTree (rootl,nums); cout<<"Binary Tree l :-"<<endl; inorder (rootl); cout<<endl; root2 = insert (root2,9); root2 = insert (root2,8); root2 = insert (root2,7); root2 = insert (root2,6); root2 = insert (root2,5); cout<<"Binary Tree 2 :-"<<endl; inorder (root2): cout<<endl; cmp = compareTree (rootl, root2); cout<<"Result = "<<cmp<<endl; return 0; 1 1 1 1 1 1 0 1 0 O M Console Enter Limit: 4 Enter an Integer: 9 Enter an Integer: 8 Enter an Integer: 7 Enter an Integer: 6 Vector of Integers:- 9 8 7 6 5 Binary Tree 1 :- 5 6 7 8 9 Binary Tree 2 :- 5 6 7 8 9 Result = 0 <<< Process finished (PID=10640). (Exit code 0) ================ READY ================ C++ source file length : 3,409 lines : 175 Ln : 156 Col:27 Sel: 010 Windows (CRLE) UTF-8 SINS INS 1 Type here to search ^ ( rue ENG 10:22 PM 20-04-2020