TREEORD - Tree _order - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : TREEORD

👉 Hint : edit please

✅ C++ Solution :

 
#include <bits/stdc++.h>
using namespace std;
struct btnode
{
	int info,count;
	struct btnode *lchild,*rchild;
};
int preindex=0;
int postindex;
typedef struct btnode BTNODE;
int i=0;
int arr[8001];
void postor(BTNODE *root)
{
	if(root!=NULL)
	{
		postor(root->lchild);
		postor(root->rchild);
		printf("%d ",root->info);
	}
}
void postord(BTNODE *root)
{
	if(root!=NULL)
	{
		postord(root->lchild);
		postord(root->rchild);
		arr[i++]=root->info;
	}
}

void preord(BTNODE *root)
{

	if(root!=NULL)
	{
	   	printf("%d ",root->info);
		preord(root->lchild);
		preord(root->rchild);
	}
}

BTNODE *insert(BTNODE *root,int x)
{
	if(root==NULL)
	{
		root=(BTNODE *)malloc(sizeof(BTNODE));
		root->count=1;
		root->info=x;
		root->lchild=NULL;
		root->rchild=NULL;
		//printf("%d",root->info);
		
	}
	else if(x < root->info)
		root->lchild=insert(root->lchild,x);
	else if (x > root->info)
		root->rchild=insert(root->rchild,x);
	else
		root->count++;
	

	return root;
}
int search(int in[20],int start,int end,int val)
{
	int i;
	for(i=start;i<=end;i++)
	{
		if(in[i]==val)
			return i;
	}
	return -1;
}	
BTNODE *constPre(int in[20],int pre[20],int start,int end )
{
	if(start>end)
		return NULL;
	
	BTNODE *ne=(BTNODE*)malloc(sizeof(BTNODE));	
	ne->info=pre[preindex++];
	if(start==end)	
		return ne;
	int inIndex=search(in,start,end,ne->info);
	
	ne->lchild=constPre(in,pre,start,inIndex-1);
	ne->rchild=constPre(in,pre,inIndex+1,end);	
	
	return ne;
}
				
int post(BTNODE *root,int postorder[],int n)
{
    postord(root);
    for(int i=0;i<n;i++)
    {
        if(arr[i]!=postorder[i])
            return 0;
    }
    return 1;
}
		
	
	
int main()
{
	BTNODE *root=NULL;
	int n;
	cin>>n;
	int inorder[n],preorder[n],postorder[n];
	for(int i=0;i<n;i++)
		cin>>preorder[i];
	for(int i=0;i<n;i++)
		cin>>postorder[i];
	for(int i=0;i<n;i++)
		cin>>inorder[i];
	root = constPre(inorder,preorder,0,n-1);
    //postor(root);
	if(post(root,postorder,n))
		cout<<"yes";
	else
		cout<<"no";
	return 0;
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.