If you are given two traversal sequences, can you construct the binary tree?

It all depends on what tree traversals are given.

Following tree traversals in conjunction can be used to create the binary tree.

Inorder and preorder

Inorder and postorder

Inorder and level order

All the combinations of tree traversals other than the above will not be able to used to generate the exact tree.

Here is the program given Inorder and preorder. In the similar lines one can write a program for Inorder and postorder also.

node* BST::buildTree(int *in, int inStrt, int inEnd, int len, int *pre)

{

if(preIndex >= len || inStrt > inEnd)

return NULL;

node *retNode = makeNode(pre[preIn dex++]);

if(inStrt == inEnd)

return retNode;

int inIndex = findNodeIn(in, inStrt, inEnd, retNode->data);

retNode->left = buildTree(in, inStrt, inIndex - 1, len, pre);

retNode->right = buildTree(in, inIndex+1, inEnd, len,pre);

return retNode;

}

int BST::findNodeIn(int* in, int inStrt, int inEnd, int value)

{

int i = inStrt;

for(;i<=inEnd;i++

if(in[i] == value)

return i;

}

int preIndex;

int main()

{

preIndex = 0;

int in[] = {1,2,3,4,5,7,8};

int pre[] = {4,2,1,3,7,5,8};

root = buildTree(in,0,6,7,pre);

}