CareerCup

typedef struct node
{
	node *left;
	node *right;
	int num;
} Node;

Node *ConstructTree(int *preorder,int *inorder,int len)
{
	Node *n = new Node;
	n->num = preorder[0];
	n->left = NULL;
	n->right = NULL;
	if(len == 1)
		return n;

	int mid = 0;
	for(int i=0; i<len; i++)
	{
		if(preorder[0] == inorder[i])
			break;
		mid++;
	}

	if(mid > 0)
		n->left = ConstructTree(&preorder[1],inorder,mid);
	if(len-mid > 1)
		n->right = ConstructTree(&preorder[mid+1], 						&inorder[mid+1],len-1-mid);
	return n;
}

It is possible to create a BST from inorder and preorder/postorder traversal.
There is no way in this world by which you can create BST using preorder and postorder traversal.

yeah it is possible to create a BST given only pre-order but not with post-order

You can get original BST for preorder.

but not for only inorder. You get multiple trees
ex.
Following trees have BST's have same inorder i.e 1,2,3,4,5,6
4
/ \
2 6
/ \ /
1 3 5

4
/ \
2 5
/ \ \
1 3 6

Constructing from inorder and pre order
1. take first element from preorder and split inorder in to leftsubtree and right subtree
2. split above left and right subtrees in recurssion by picking next element from preorder

// Trees.cpp : Program constuct a binary Tree taking inorder and preorder traversal input
//

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "memory.h"
#include "string.h"

struct Node
{
char Data;
struct Node* Left;
struct Node* Right;
};

struct Node* CreateNewNode(char data)
{
struct Node* NewNode = NULL;
NewNode= (struct Node*) malloc (sizeof(struct Node));
if (NULL != NewNode )
{
NewNode->Data = data;
NewNode->Left = NULL;
NewNode->Right = NULL;
}
return (NewNode);
}

void PrintInOrder(struct Node* head)
{
if (NULL != head)
{
PrintInOrder(head->Left);
printf(" %c ",head->Data);
PrintInOrder(head->Right);
}
}

void PrintPreOrder(struct Node* head)
{
if (NULL != head)
{
printf(" %c ",head->Data);
PrintPreOrder(head->Left);
PrintPreOrder(head->Right);
}
}

void PrintPostOrder(struct Node* head)
{
if (NULL != head)
{
PrintPostOrder(head->Left);
PrintPostOrder(head->Right);
printf(" %c ",head->Data);
}
}
// Split inorder input in to left subtree and right subtree w.r.t root node C taken from
//pre order
bool SplitLeftRightSubTree(const char* pInput, char c, char* pLeftSubTree,char* pRightSubTree)
{
unsigned int StrLength = 0 ;
if (NULL == pInput || NULL == pLeftSubTree || NULL == pRightSubTree)
{
return false;
}
StrLength = strlen(pInput) ;
if (0 == StrLength || 1 == StrLength) //no need to split
{
return false;
}
int i=0;
for(; pInput[i] != c && pInput[i] != '\0' ; i++)
{
pLeftSubTree[i] = pInput[i];
}
pLeftSubTree[i] = '\0' ;
if (pInput[i] != c)
{
return false; //invalid input c has to be present in input
}
i++;
if (i == StrLength) //there is nothing after C
{
pRightSubTree[0] = '\0' ;
return true;
}
else
{
int j=0;
for(; pInput[i] != '\0'; i++,j++)
{
pRightSubTree[j] = pInput[i] ;
}
pRightSubTree[j] = '\0' ;
return true;
}
}

struct Node* BuildBinaryTree(const char* pInOrder, char* pPreOrder)
{
struct Node* Head = NULL;
static unsigned int PreIndex = 0;
if (NULL == pInOrder || NULL == pPreOrder)
{
return NULL;
}
unsigned int InOrderLength = strlen(pInOrder);
if ( 0 == InOrderLength)
{
return NULL;
}
if (1== InOrderLength)
{
//creates child nodes left/right in recurssion
PreIndex++;
return CreateNewNode(*pInOrder);
}

char *pLeftSubTree = NULL,*pRightSubTree = NULL;
pLeftSubTree = (char*) malloc (sizeof(char)*strlen(pInOrder));
if (NULL == pLeftSubTree)
{
//memory allocation failure, return
return NULL;
}
pRightSubTree = (char*) malloc (sizeof(char)*strlen(pInOrder));
if (NULL == pRightSubTree)
{
//memory allocation failure, free the prev allocation and return
free(pLeftSubTree) ;
pLeftSubTree = NULL;
return NULL;
}
//Split the left sub tree and right sub tree
if (SplitLeftRightSubTree(pInOrder,pPreOrder[PreIndex],pLeftSubTree,pRightSubTree))
{
//creates parent nodes in recurssion
Head = CreateNewNode(pPreOrder[PreIndex++]);

if (pLeftSubTree != NULL && strlen(pLeftSubTree) != 0)
{
Head->Left = BuildBinaryTree(pLeftSubTree,pPreOrder);
}
if (pRightSubTree != NULL && strlen(pRightSubTree) != 0)
{
Head->Right = BuildBinaryTree(pRightSubTree,pPreOrder);
}
}
else
{
printf("invalid inorder and pre order input");
return NULL;
}
//free the dynamically alocated memory
free(pLeftSubTree);
pLeftSubTree = NULL;
free(pRightSubTree);
pRightSubTree = NULL;

return Head;
}

int _tmain(int argc, _TCHAR* argv[])
{
char* pInOrder = "1234567" ;
char* pPreOrder = "4213657" ;
struct Node* NewBST = NULL;
NewBST = BuildBinaryTree(pInOrder,pPreOrder);
printf("\n In Order ");
PrintInOrder(NewBST);
printf("\n Pre Order ");
PrintPreOrder(NewBST);
getchar();
return 0;
}

geeksforgeeks . org/ ?p=6633

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
struct bin_tree{
            char data;
            struct bin_tree *right;
            struct bin_tree *left;
            };
typedef struct bin_tree node;
 node * newNode(char a)
{      node *temp=(node *)malloc(sizeof(node));
        temp->right=NULL;
        temp->left=NULL;
        temp->data=a;
        return temp;

};
int find(char *str, char a)
{   int i=0;
    for(i=0;i<strlen(str);i++)
     {
         if(str[i]==a)
         return i;
     }
};
 node * create(char *inor,char *pre,int in_start,int in_end,int pre_start,int pre_end)
{       int len=(in_end-in_start)+(pre_end-pre_start);
        if(len>=0)
        { char temp=pre[pre_start];
           node *root=newNode(temp);
          int ind=find(inor,temp);
          int siz_left=in_end-ind;
          //cout<<"holo";
          root->left=create(inor,pre,in_start,ind-1,pre_start+1,pre_end-siz_left);
          root->right=create(inor,pre,ind+1,ind+siz_left,pre_end-siz_left+1,pre_end);
          return root;
        }
        else
        return NULL;

};
void display(node *root)
{   if(root!=NULL)
    {   display(root->left);
        cout<<root->data<<" ";
        display(root->right);
    }

}
int main()
{       node *root=NULL;
        char arr1[8]="cbfdgae";
        char arr2[8]="abcdfge";
        root=create(arr1,arr2,0,6,0,6);
        display(root);
        return 0;

}