Finding the other two traversals of a Binary Tree when given only one traversal

Question

I know you can reconstruct a binary tree when given its inorder and preorder traversals as strings, but is it possible to find the postorder and/or preoder traversals when only given the inorder traversal?

Answer 1

No, retrieving postorder/preorder from only inorder traversal is not possible. If it was, it would be possible to reconstruct a binary tree with only the inorder traversal, which is not possible because one inorder traversal can give you several possible reconstructed binary trees.

Answer 2

How does your input look like, and what is the purpose of the tree?

If you have a fully parenthesized in-order expression, then you have a uniqe tree, and you get pre- and post-order by constructing the tree and then constructing the pre- and post-order terms from the tree.

If your expression is not fully parenthesized, then this is an indication that there is no difference between the different trees that match your in-order. E.g If it's a tree representing arithmetical expressions, then x+y+zis the same as (x+y)+z and x+(y+z). This however means, it does not matter which pre- or postorder you use, also ++xyzand +x+yzare the same.

Now if this doesn't matter, you do not need to worry about several posssible representations of your in-order. Just choose one of the representations, and then compute the pre- and post-order induced by this tree.