CareerCup

How if you have the following in-order sequence:
4 8 10 6 20 5 9 7 3
Yes, we could get the root from the middle of above sequence but the next the recursion is little bit shaky - on the second recursion we have two set of sequences, on the left is 4 8 10 6 and on the right is 5 9 7 3. We know we should choose 10 from the left sequence and 9 on the right sequence but 10 is 3rd element of the left sequence while 9 is the 2nd element of the right sequence.

Therefore, to fix that issue on the next recursion, instead of looking at the middle, we should look up for the biggest number on the sequence. Then it will work nicely.

I think this is a classic question
Yes.. it is possible to build a heap tree only from its inorder..
Cosider the following case..

20
                         /        \
                       10       9
                      /   \       /  \
                     8   6    3   2
                    /
                  4

Its inorder is        4 8 10 6 20 3 9 2

root will be the middle element. i.e. 20

recurse the same function on left tree(4,8,10,6)  and right tree(3,9,2)

tree is constructed..

refer careercup.com/question?id=9735293

int find_max(int a[],int low,int high)
{ int max=0,index;
for(int i=low;i<=high;i++)
{
if(a[i]>max)
{
max=a[i];
index=i;
}
}
return index;
}
void addnode(int a[],int low,int high,node **root,node **ptr)
{
int k;
if(low>high)
return ;
else
{
node *temp= new node;
k=find_max(a,low,high);
temp->data=a[k];
temp->left=NULL;
temp->right=NULL;
if ( *root == NULL)
*root = temp;
*ptr=temp;
addnode(a,low,k-1,root,&(*ptr)->left);
addnode(a,k+1,high,root,&(*ptr)->right);
}
}