CareerCup

call this method with start=0, end=in.Lengh;

Node* ConstructTree(char in[], char pre[], int start, int end)
{
int preIndex = 0;
Node * node = newNode(pre[preIndex++]);

if(start == end)
return node;

int index = Search(in, start, end, node->data);

node->left = ConstructTree(in, pre, start, index-1);
node->right = ConstructTree(in, pre, index-1, end);

return node;

}

So, the Inorder (Left Root Right) is: 5 3 2 4 1 7 6
and Pre order (Root Left Right): 1 2 3 5 4 6 7

In preorder, we will print the root first. So 1 will be the root. In inorder, search for 1. the elements towards the left are
elements in the left subtree and towards the right are in the right sub tree.

Consider the next element in Preorder ie 2. 2 is in left subtree(LST) of 1. So it will be the left child of 1.
The next element in preorder is 3. This is in LST of 1 as well as 2 so it will be the left child of 2.
Similar is the case with 5.
Coming to 4, it is in the LST of 1 but in RST of 2. So will be the right child of 2.
Do the same with 6 and 7.

it does not look a binary tree

// This problem should confine the value of every element in this BinaryTree is different.
// Or you can not reconstruct A BinaryTree by using Pre-order and In-order Array.

public class Pre_In_Order_Of_Tree_Reconstruct_Tree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public static void showPre(Node head){
if(head==null){
return ;
}
System.out.print(head.value+" ");
showPre(head.left);
showPre(head.right);
}
public static void showIn(Node head){
if(head==null){
return ;
}
showIn(head.left);
System.out.print(head.value+" ");
showIn(head.right);
}

public static Node reconTree(int[] Pre,int[] In){
Node result=compute_process(Pre,In,0,0,In.length-1);
return result;
}

public static Node compute_process(int[] Pre,int[] In,int PreIndex,int Inbegin,int Inend){
if(PreIndex>=Pre.length){
return null;
}
if(Inbegin==Inend){
return new Node(Pre[PreIndex]);
}
Node head=new Node(Pre[PreIndex]);
int num=findPosition(In,Inbegin,Inend,Pre[PreIndex]);
if(num==0){
head.left=null;
}
else{
head.left=compute_process(Pre,In,PreIndex+1,Inbegin,Inbegin+num-1);
}
if(num==Inend-Inbegin+1){
head.right=null;
}
else{
head.right=compute_process(Pre,In,PreIndex+num+1,Inbegin+num+1,Inend);
}
return head;
}
public static int findPosition(int[] In,int Inbegin,int Inend,int aim){
int num=0;
for(int i=Inbegin;i<=Inend;i++){
if(In[i]!=aim){
num++;
}
else{
break;
}
}
return num;
}
public static void main(String[] args) {

int[] Pre = {8,7,3,1,2,9,10,6,4,12};
int[] In = {3,7,1,2,8,9,6,4,10,12};
Node head=reconTree(Pre,In);
showPre(head);
System.out.println();
showIn(head);

}

}

i agree that this prob is incomplete that the structure of the BT should be restricted to a form because one just simply can't inference a BT given a traversal result.

if it has the certain form given, we can then simply fill out the blanks in fixed positions in the array first by making it false even. .. then follow the reversed pattern we can reconstruct the BT.

This is a non-recursive code.

//Concept:
Assuming both pre-order and in-order are written left to right;
For every element aplha and its immediate right element beta in pre-order 
     If beta occurs left (need not be immediate) of alpha in in-order; 
           implies  alpha -> left-child = beta
     Else-If beta occurs IMMEDIATE right of alpha in in-order; implies  
            alpha -> right-child = beta
     Else
	//Otherwise there exists elements in between alpha and beta in 
	//in-order and beta is right of alpha. Consider e.g.  
	//... alpha (alpha_1, alpha_2, .. alpha_m ) beta .. is the 
	// element-sequence in in-order
        Find the right most of all alpha_x such that it also exists in 
	       the parent probing stating at last node evaluated
	If NO such alpha_x is found 
		then alpha -> right-child = beta 
        Else
	        alpha_x -> right-child = beta


//----- Pseudo Code (Runtime: O( nln(n) ) n=number of nodes in tree) ----
int i = positio of pre_t[0] in in_t[]
Node root=createNode(pre_t[0])
Node n=root;

for j=0 upto j=len-2      //len=length(pre_t)
    ii=getLeftPosition(in_t, i, pre_t[j+1]) // returns index of pre_t[j+1] in 
				// in_t[] searching all positions left 
				// of i; returns -1 if not found 

    if ii > 0 
	n->left=createNode(pre_t[j+1])
	i=ii; n=n->left; 
	continue; 
    end-if


    if pre_t[j+1] == in_t[i+1]     //next right element of j in pre_t is  also 
                                   // IMMEDIATE right element in in_t
	n->right=createNode(pre_t[j+1])
	i=i+1; n=n->right; 
	continue; 
    end-if

    Node t=n->parent;
    while t exists
	r,m = getRightPosition(in_t, i, t, pre_t[j+1]) //search in_t for all 
	                    // positions on the right of i (excluding i)
	                    // if t->val is encountered before pre_t[j+1]
			    //    then return  r = index of t->val, m = -1
			    // else
			    //    return   r = -1, m = index of pre_t[j+1]
	if r == -1
	     n->right = createNode(pre_t[j+1])
	     i=m; n=n->right; 
	     break while-loop 
	end-if

	n=t; i=r;
    end-while-loop

end-for-loop

return root;