Minal_067.cpp

#include <iostream>
#include <vector>
using namespace std;

struct BSTNode
{
    int data;
    BSTNode* LChild;
    BSTNode* RChild;

    BSTNode(int val){
        data = val;
    }
} *root = NULL;
BSTNode* insert(BSTNode* node, int value){
    if (node == NULL)
    {
        BSTNode* temp = (BSTNode*)malloc(sizeof(BSTNode));
        temp->data = value;
        temp->LChild = NULL;
        temp->RChild = NULL;
        return temp;
    }
    if (value < node->data)
    {
        node->LChild = insert(node->LChild,value);
    }
    else{
        node->RChild = insert(node->RChild,value);
    }
    return node;
}
void preOrder(BSTNode* node){
    if (node != NULL)
    {
        cout<<node->data<<" ";
        preOrder(node->LChild);
        preOrder(node->RChild);
    }
    
}
void createSubtrees(int* arr,int low, int high,int index,vector<int>s1,vector<int>s2,vector<int>s3,vector<int>s4){
    int mid = (low + high)/2;
    int index1 = mid/2;
    int index2 = (3*mid)/2;
    int l = low;
    int h = h;
    if (l == h)
    {
        return;
    }
    if(arr[index] <= arr[index1]){
        s1.push_back(arr[index]);
    }
    else if(arr[index] > arr[index1] && arr[index]< root->data)
    {
        s2.push_back(arr[index]);
    }
    else if(arr[index] > root->data && arr[index]< arr[index2])
    {
        s3.push_back(arr[index]);
    }
    else
    {
        s4.push_back(arr[index]);
    }
    createSubtrees(arr,low,mid,++index,s1,s2,s3,s4);
    createSubtrees(arr,mid+1,high,++index,s1,s2,s3,s4);
}
int main(int argc, char const *argv[])
{
    int S[11] = {22,44,75,90,92,99,110,112,125,130,131};
    vector<int>s1;
    vector<int>s2;
    vector<int>s3;
    vector<int>s4;
    root = insert(root,S[(0+11)/2]);
    createSubtrees(S,0,11,0,s1,s2,s3,s4);
    int mid1 = (s1.size() + 0)/2;
    int mid2 = (s2.size() + 0)/2;
    int mid3 = (s3.size() + 0)/2;
    int mid4 = (s4.size() + 0)/2;
    root = insert(root,S[mid1]);
    root = insert(root,S[mid2]);
    root = insert(root,S[mid3]);
    root = insert(root,S[mid4]);
    preOrder(root);
    return 0;
}