Preorder and relation to Inorder Traversal

Question

I find that if we have Preorder and Inorder Traversal, we have a unique tree.

can i conclude:

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.

thanks again.

Answer 1

Yes because from a single preorder sequence you can create multiple trees. For instance: [4,3,1, 2] can be repesented as a tree with root 4, children 3 and 2. Then you can insert 1 as either left or right child of 3. Depending on where you will insert it the inorder sequence will change.

You can also reason about it in this way: you have n numbers, with them you can get n! permutations. Generating a tree from your traversal would be possible if the number of permutations was equal to the number of possible trees you can create usin those n numbers. This is not the case, though as you can for instance create many trees, where every node has only a left child or only a right child, this gives you 2*n! and there are more so there has to be a permutation that can generate more than 1 tree => more than 1 inorder traversal.

This is of course true in general case, BSTs have a unique inorder sequence.