Tree construction from Inorder & Preorder [ Microsoft ]

Problem:

Provided Inorder and PreOrder of a tree. Construct the tree and print it in PostOrder traversal.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include<stdlib.h>
#include <string>

using namespace std;

int preOrderIdx=0;

struct Node{
	int data;
	Node *left;
	Node *rit;
};


int search(int in[],int in_stIndex,int in_endIndex,int data)
{
	for(int i=in_stIndex;i<=in_endIndex;i++)
	{
		if(in[i]==data)
		return i;
	}
}

Node* buildTree(int in[],int pre[],int in_stIndex,int in_endIndex)
{
	//static int preOrderIdx=0;
	if(in_stIndex>in_endIndex)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=pre[preOrderIdx++];
	tNode->left=NULL;
	tNode->rit=NULL;
	if(in_stIndex==in_endIndex)
	return tNode;
	int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data);
	
	tNode->left=buildTree(in,pre,in_stIndex,rootIndex-1);
	tNode->rit=buildTree(in,pre,rootIndex+1,in_endIndex);
	return tNode;
}

void pintPostOrder(Node* res)
{
	Node *tmp;
	if(res!=NULL)
	{
		if(res->left)
		pintPostOrder(res->left);
		if(res->rit)
		pintPostOrder(res->rit);
		cout<<res->data<<" ";
	}
}
int main()
{
	int in[105];
	int pre[105];
	int t,n;
	scanf("%d",&t);
	Node *res,*tmp;
	while(t--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%d",&in[i]);
		for(int i=0;i<n;i++)
			scanf("%d",&pre[i]);
		res=buildTree(in,pre,0,n-1);
		pintPostOrder(res);
	}
	return 0;
}

The problem was provided as a functional problem in Microsoft interview as here  [Courtesy : geeksforgeeks]

Solution:

/*
Please note that it's Function problem i.e.
you need to write your solution in the form Function(s) only.
Driver Code to call/invoke your function would be added by GfG's Online Judge.*/


/*Complete the code here.
Node is as follows:
struct Node
{
  int data;
  Node* left;
  Node* right;
};
*/

int search(int in[],int in_stIndex,int in_endIndex,int data)
{
	for(int i=in_stIndex;i<=in_endIndex;i++)
	{
		if(in[i]==data)
		return i;
	}
}

Node* newbuildTree(int in[],int pre[], int inStrt, int inEnd,int *preOrderIdx)
{
	if(inStrt>inEnd)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=pre[(*preOrderIdx)++];
	tNode->left=NULL;
	tNode->right=NULL;
	if(inStrt==inEnd)
	return tNode;
	int rootIndex = search(in,inStrt,inEnd,tNode->data);
	
	tNode->left=newbuildTree(in,pre,inStrt,rootIndex-1,preOrderIdx);
	tNode->right=newbuildTree(in,pre,rootIndex+1,inEnd,preOrderIdx);
	return tNode;
}
Node* buildTree(int in[],int pre[], int inStrt, int inEnd)
{
//add code here.
    int preOrderIdx=0;
    newbuildTree(in,pre, inStrt,inEnd,&preOrderIdx);
}