Tree construction a Binary Tree from Postorder and Inorder traversal [Amazon, Adobe]

Problem:

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

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

using namespace std;


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;
	}
}

void pintPreOrder(Node* res)
{
	Node *tmp;
	if(res!=NULL)
	{
		cout<<res->data<<" ";
		if(res->left)
		pintPreOrder(res->left);
		if(res->right)
		pintPreOrder(res->right);
	}
}
Node* NewbuildTree(int in[],int post[],int in_stIndex,int in_endIndex,int *postOrderIdx)
{
	
	if(in_stIndex>in_endIndex)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=post[(*postOrderIdx)--];
	tNode->left=NULL;
	tNode->right=NULL;
	if(in_stIndex==in_endIndex)
	return tNode;
	int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data);
	
	tNode->right=NewbuildTree(in,post,rootIndex+1,in_endIndex,postOrderIdx);
	tNode->left=NewbuildTree(in,post,in_stIndex,rootIndex-1,postOrderIdx);
	return tNode;
}

Node *buildTree(int in[], int post[], int n)
{
	int postOrderIdx=n-1;
	NewbuildTree(in,post,0,n-1,&postOrderIdx);
}

int main()
{
	int in[105];
	int post[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",&post[i]);
		res=buildTree(in,post,n);
		//cout<<"done"<<endl;
		pintPreOrder(res);
	}
	return 0;
}

The problem was provided as a functional problem in Amazon & Adobe interview as here  [Courtesy : geeksforgeeks]

Solution:

struct Node 
{
   int data;
   Node *left, *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 post[],int in_stIndex,int in_endIndex,int *postOrderIdx)
{
	
	if(in_stIndex>in_endIndex)
	return NULL;
		
	Node *tNode = new Node();
	tNode->data=post[(*postOrderIdx)--];
	tNode->left=NULL;
	tNode->right=NULL;
	if(in_stIndex==in_endIndex)
	return tNode;
	int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data);
	
	tNode->right=NewbuildTree(in,post,rootIndex+1,in_endIndex,postOrderIdx);
	tNode->left=NewbuildTree(in,post,in_stIndex,rootIndex-1,postOrderIdx);
	return tNode;
}
// Function should construct tree and return
// root of it.  in[] stores inorder traversal
// post[] stores postorder traversal.  n is
// size of these arrays
Node *buildTree(int in[], int post[], int n)
{
    // Your code here
    int postOrderIdx=n-1;
	NewbuildTree(in,post,0,n-1,&postOrderIdx);
}