I'm given an in-order traversal and need to find a binary tree. I referred my sites and most of them said it is not possible. However, i think a non-unique binary tree is possible. Can i find a binary tree using just given in-order traversal? If not, can i find a corresponding pre-order traversal from the given in-order traversal?
I tried to convert the in-order into pre-order by selecting the central node of in-order as the root but I'm not sure if its correct. Please guide me.
Thank you.
Given just the in-order traversal of the nodes, and no more information in the question, you can find a binary tree, but as you said, there won't be a unique solution (especially if the tree doesn't have to be balanced). As a result, you can again find a pre-order traversal.
As an example, if your in-order traversal is [1,2,3,4,5,6,7,8], then even if the tree is balanced, there are multiple possibilities for the root node (namely, 4 or 5). If the tree doesn't have to be balanced, you could potentially pick any of these as the root node.
Here's an example of a non-balanced tree you could build after arbitrarily choosing 4 as the root node:
4
/ \
3 6
/ / \
2 5 7
/ \
1 8
Pre-order traversal for this tree would yield 4,3,2,1,6,5,7,8. Again, if the only requirements are that you just find a binary tree, this is just as valid as setting 1 as the root node and making everything else a right node:
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
The pre-order traversal for this tree would be 1,2,3,4,5,6,7,8. Since these trees both generate the same in-order traversal, but different pre-order traversals, there isn't guaranteed to be a single, unique tree or even a single, unique pre-order traversal for a given in-order traversal.
