CareerCup

6
4 8
3 5 7 9
ps={3547986}
nodetye={LLILLII}
Algo for creating binary tree

if(nodetype.length == 1){ // array has only one element hence it is head
return ps[0];
}
//iterate thrugh array and if nodetype is 'L' push it into stack , else pop last two elements from the stack and make it as right and left child of the current element push current element on to stack , in the end only root will be in the stack
for(int i=0; i < nodeType.lenght;i++){
	if(nodeType[i]=='L'){
	stack.push(ps[i]);
	}else{
	node right = stack.pop();
	node left=stock.pop();
	node element=ps[i];
	element.right=right;
	element.left=left;
	stack.push(element);
	}
}

return stack.pop();
}

6
4 8
3 5 7 9
{3547986}
{LLILLII} // I dont find any use for this information , probably can be used for data verification
{0 - n-1}
top=n-1

constructBTree(post[n])
{
top=n-1;
root=post[top];
if(size(post) == 1)
return root;
if(z)
leftTop=top-1;
while(root < post[leftTop] && leftTop != 0)
leftTop--;
if(leftTop != 0)
root->left = constructBTree(post[0....leftTop-1]);
else
root->left = null;

if(leftTop < top-1)
root->right = constructBTree(post[leftTop....top-1]);
else
root->right = null;
}

If I am correct, we will be given a post order tree like below:
LLILLII or LLILLILLIII.

For this they have given a condition that a node can have 0 or 2 children compulsory.

Algo for constructing a BinaryTreeNode in Java Language :

BinaryTreeFromPostOrder(char[] A, int i){

	if(A == null){
		return null;
	}

	BinaryTreeNode new Node = new BinaryTreeNode();
	newNode.setData(A[i]);
	newNode.setLeft(null);
	newNode.setRight(null);

	if(A[i] == 'L'){
		return newNode;
	}

	i = i - 1;
	newNode.setRight(BuildTreeFromPostOrder(A,i));
	
	i = i - 1;
	newNode.setLeft(BuildTreeFromPostOrder(A,i));
	
	return newNode;

}

Call this method with BinaryTreeFromPostOrder(A, A.length-1);


Let me know if I did any thing wrong or if I understood the question wrongly.

Thanks,
Ranjith

If you are give the postfix in an array in the form like
a[]={i,i,n,i,n,n} and another array that denotes the node like
b[]={2,3,4,5,6,7} then you can make the binary tree using recursion as:

tree *makeBinaryTree(char a[],int b[],int *index,int n)
{
	int indx=*index;
        if(indx==n)
            return NULL;
	tree *n=makeNewNode(a[indx]);
	*index++;
	if(b[indx]=='i')
	{
		n->left=makeBinaryTree(n,a,b,index);
		n->right=makeBinaryTree(n,a,b,index);
	}
	return n;
}

if given array is post-order then start processing from end of the array and first insert right child and then left child

if given array is pre-order then start processing from start of the array and first insert left child and then right child

initially sz = length of array - 1 (for given post-order array)

void insert(node **root, char arr[], int &sz)
{
	*root = new node;
	(*root)->data = arr[sz];
	(*root)->left = (*root)->right = NULL;

	if(arr[sz] == 'i')
	{
		insert(&(*root)->right, arr, --sz);
		insert(&(*root)->left, arr, --sz);
	}
}

First of all let me clarify the question: my understanding is that the tree generated by *postorder* traversal is given by the "i"-"l" array (or what exactly does the post-fix mean here?). If this understanding is correct, the following is my solution.

First of all it is easy to see that the last element of the array is the root. Then the difficulty in the recursive call is to separate the left subtree from the right subtree. To do so note that any tree has (number of "i") == (number of "l") - 1, therefore we can scan from the 2nd from the last element backwards and count the number of "i" and "l", until we have the condition (number of "i") == (number of "l") - 1 satisfied, and this will be the right subtree, and the rest is the left subtree.

Steps: (Let p and q be start and end position in postorder array)
1. Since the last element is root. we need to create a node postorder[r];
2. q=(p+r)/2;
3. Left subtree (postorder[1...q-1])
4 Right subtree(postorder[q+1 ... r])
The mistake I did was while constructing the tree , I had forgotten create the node at base case. Now I have rectified it . Attaching my code.

void construct_tree_postorder(int *postorder,int p,int r,struct node** tree)
{
    int x=postorder[r];
    if(r<p)
        return;
    if(r==p) // base case only root
    {
        (*tree)=create_a_node(postorder[r]);
         return;
    }
    else
    {
        int q = (p+r-1)/2;
        (*tree)=create_a_node(postorder[r]);
        construct_tree_postorder(postorder,q+1,r-1,&((*tree)->right));
        construct_tree_postorder(postorder,p,q,&((*tree)->left));
        return;
    }
}