24th December 2022

 The implementation of how to use PreOrder and PostOrder Traversals alongwith InOrder to generate a Tree.

#include <bits/stdc++.h>

#define fastio std::ios_base ::sync_with_stdio(false);std::cin.tie(NULL);std::cout.tie(NULL);std::cout << std::fixed << std::setprecision(25);

using namespace std;

template<typename T>

struct node{

    T value;

    struct node* left;

    struct node* right;

};

struct node<int>* make_node(int val){

    struct node<int>* node=(struct node<int>*)malloc(sizeof(struct node<int>));

    if(node==NULL){

        return NULL;

    }

    node->value=val;

    node->left=NULL;

    node->right=NULL;

    return node;

}

int find_root(vector<int> in,int val){

    int n=in.size();

    for(int i=0;i<n;i++){

        if(in[i]==val){

            return i;

        }

    }

    return -1;

} 

struct node<int>* pre_to_in(vector<int> pre,vector<int> in,int l,int r){

    static int ptr=0;

    if(l>r){

        return NULL;

    }

    int data=pre[ptr];

    ptr++;

    int ind=find_root(in,data);

    struct node<int>* n1=make_node(data);

    if(l==r){

        return n1;

    }

    n1->left=pre_to_in(pre,in,l,ind-1);

    n1->right=pre_to_in(pre,in,ind+1,r);

    return n1;

}

void preOrd(struct node<int>* root){

    if(root!=NULL){

        cout<<root->value<<" ";

        preOrd(root->left);

        preOrd(root->right);

    }

}

void inOrd(struct node<int>* root){

    if(root!=NULL){

        inOrd(root->left);

        cout<<root->value<<" ";

        inOrd(root->right);

    }

}

struct node<int>* pos_and_in(vector<int> pos,vector<int> in,int l,int r){

    static int it=r;

    int data=pos[r];

    it--;

    if(l>r){

        return NULL;

    }

    int ind=find_root(in,data);

    struct node<int>* node=make_node(data);

    if(l==r){

        return node;

    }

    node->right=pos_and_in(pos,in,l,ind-1);

    node->left=pos_and_in(pos,in,ind+1,r);

    return node;

}

struct node<int>* pre_to_inorder(vector<int> pre,vector<int> in,int l,int r){

    static int it=0;

    if(l>r){

        return NULL;

    }

    int data=pre[it];

    it++;

    int pos=find_root(in,data);

    struct node<int>* nod=make_node(data);

    if(l==r){

        return nod;

    }

    nod->left=pre_to_inorder(pre,in,l,pos-1);

    nod->right=pre_to_inorder(pre,in,pos+1,r);

    return nod;

}

void posOrd(struct node<int>* root){

    if(root!=NULL){

        posOrd(root->left);

        posOrd(root->right);

        cout<<root->value<<" ";

    }

}

int32_t main() {

    fastio

    vector<int> pre={

      12, 23, 13, 100, 40, 50, 7 

    },ino={

      13, 23, 100, 12, 50, 40, 7 

    },pos{

        13,100,23,50,7,40,12

    };

    // struct node<int>* n1=pos_and_in(pre,ino,0,6);

    // posOrd(n1);

    // cout<<endl;

    // preOrd(n1);

    // cout<<endl;

    // inOrd(n1);

    // cout<<endl;

    struct node<int>* n1=make_node(12);

    struct node<int>* n2=make_node(23);

    struct node<int>* n3=make_node(40);

    n1->left=n2;

    n1->right=n3;

    struct node<int>* n4=make_node(7);

    struct node<int>* n7=make_node(50);

    n3->left=n4;

    n3->right=n7;

    struct node<int>* n5=make_node(100);

    struct node<int>* n6=make_node(13);

    n2->left=n6;

    n2->right=n5;

    posOrd(n1);

    cout<<endl;

    preOrd(n1);

    cout<<endl;

    inOrd(n1);

    cout<<endl;

    

    

    // struct node<int>* n1=make_node(100);

    // if(n1==NULL){

    //     return -1;

    // }

    // cout<<n1->value<<endl;
    // struct node<int>* n1=(struct node<int>*)malloc(sizeof(struct node<int>));

    // n1->value=100;

    // n1->left=NULL;

    // n1->right=NULL;

    cout<<"Hola Todo El Mundo!\n";

    // return (int)'d';

    return -5;

}

Comments

Popular Posts