Question

Write C++ program (submit the .cpp,.h, .sln and .vcxproj files)

Problem 1. Generate 100 random numbers of the values 1-20 in an input.txt. Now create a binary search tree using the numbers of the sequence. The tree set should not have any nodes with same values and all repeated numbers of the random sequence must be stored in the node as a counter variable. For example, if there are five 20s’ in the random sequence then the tree node having data 20 has counter variable equal to 5. Sort the sequence of numbers including repeat numbers using Binary Tree traversal.

Problem 2. Build a binary tree using a binary tree class member function from the following array of preorder traversal 3,9,20,15,7 and inorder traversal 9,3,15,20,7. Implement the constructor, destructor and all member functions including print postorder traversal of the binary tree.

Answer 1

Solution to problem 1:-

Code is as following -

#include <iostream>
#include <iomanip>

using namespace std;

struct Node{
  int val;
  int count;
  Node *left;
  Node *right;
};


Node* make_new_node(int val){
  Node *child = new Node();
  child->val = val;
  child->count = 1;
  child->left = NULL;
  child->right = NULL;
  return child;
}

//Construct the Binary search tree using the Array generated and return the root of tree
  Node * makeTree(int arr[]){
    Node *root = NULL;
    for(int i=0; i<100; i++){
      if(root==NULL){
        Node *node = make_new_node(arr[i]);
        root = node;
      }
      else{
        Node *temp = root;
        while(true){
          if(temp!=NULL){
            if(arr[i]==temp->val){
              (temp->count)++;
              break;
            }
            else
            if(arr[i]<temp->val){
              if(temp->left == NULL){
                Node *newNode = make_new_node(arr[i]);
                temp->left = newNode;
                break;
              }
              else{
                temp = temp->left;
              }
            }
            else if (arr[i] > temp->val){
              if(temp->right == NULL){
                Node *newNode = make_new_node(arr[i]);
                temp->right = newNode;
                break;
              }
              else{
                temp = temp->right;
              }
            }
          }
        }
      }
    }
    return root;
  }

int index = 0; // to store elements in sorted array

void SortUsingBinaryTraversal(Node *root,int *arr){
  if(root->left!=NULL)
    SortUsingBinaryTraversal(root->left,arr);

  for(int i=0;i<root->count;i++){
    //insert all occurences of value on current node
    arr[index++] = root->val;
  }
  if(root->right!=NULL)
   SortUsingBinaryTraversal(root->right,arr);
}

int main() {
  int arr[100];
  //generate the array of random 100 integers each having value from 1 to 20
  srand(time(0));
  for(int i=0;i<100;i++){
    int num = (rand() % 20) + 1;
    arr[i] = num;
  }

  //Print the randomly generated array in 10 by 10 matrix form
  cout<<"Randomly Generated array is:"<<endl<<endl;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      cout<<left<<setw(5)<<arr[i*10+j];
    }
    cout<<endl;
  }
  cout<<endl;

  //Construct Binary Search tree on the generated array
  Node *root = makeTree(arr);

  //Sort the array using Binary Tree Traversal
  int sortedArray[100];
  SortUsingBinaryTraversal(root,sortedArray);

  //Print Sorted array in 10 by 10 matrix form
  cout<<"Sorted Array is:"<<endl<<endl;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      cout<<left<<setw(5)<<sortedArray[i*10+j];
    }
    cout<<endl;
  }
}

Sample Output is as following:

Solution to problem (2)-

Code is as following----

#include <bits/stdc++.h> 
using namespace std; 
  
class node  
{  
    public: 
    int data;  
    node* left;  
    node* right;  
};  
  
/* Prototypes for utility functions */
int search(int arr[], int strt, int end, int value);  
node* newNode(int data); 

//Construct the tree using PreOrder and Inorder
node* buildTree(int in[], int pre[], int inStrt, int inEnd)  
{  
    static int preIndex = 0;  
    if (inStrt > inEnd)  
        return NULL;  
    node* tNode = newNode(pre[preIndex++]);  
    /* If this node has no children then return */
    if (inStrt == inEnd)  
        return tNode;  
    /* Else find the index of this node in Inorder traversal */
    int inIndex = search(in, inStrt, inEnd, tNode->data);  
    /* Using index in Inorder traversal, construct left and  
    right subtress */
    tNode->left = buildTree(in, pre, inStrt, inIndex - 1);  
    tNode->right = buildTree(in, pre, inIndex + 1, inEnd);  
    return tNode;  
}  
  
/* Function to find index of value in arr[start...end]  
The function assumes that value is present in in[] */
int search(int arr[], int strt, int end, int value)  
{  
    int i;  
    for (i = strt; i <= end; i++)  
    {  
        if (arr[i] == value)  
            return i;  
    }
    return 0;  
}  
  
/* Helper function that allocates a new node with the  
given data and NULL left and right pointers. */
node* newNode(int data)  
{  
    node* Node = new node(); 
    Node->data = data;  
    Node->left = NULL;  
    Node->right = NULL;  
    return (Node);  
}  
/* This funtcion is here just to test buildTree() */
void printPostorder(node* node)  
{  
    if (node == NULL)  
        return;  
    printPostorder(node->left); 
    printPostorder(node->right); 
    cout<<node->data<<" "; 
}  
  
/* Driver code */
int main()  
{  
    int inorder[]  = {9,3,15,20,7};  
    int preorder[] = {3,9,20,15,7};  
    int len = sizeof(inorder) / sizeof(inorder[0]);  
    node* root = buildTree(inorder, preorder, 0, len - 1);  
    cout << "PostOrder traversal of the constructed tree is \n";  
    printPostorder(root);  
}

Output is: