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.
Finding the other two traversals of a Binary Tree when given only one traversal
-
01-12-2021 - |
سؤال
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?
المحلول
نصائح أخرى
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+z
is the same as (x+y)+z
and x+(y+z)
.
This however means, it does not matter which pre- or postorder you use, also ++xyz
and +x+yz
are 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.