How to get the post order traversal of a BINARY TREE (NOT binary search tree), given only its inorder traversal
-
30-06-2021 - |
Question
I've given the result of in-order traversal of a binary tree (not binary search tree) as:
E, D, B, A, G, F, H, C
Now I've to find out the result of the post-order traversal of the same tree for which the in-order traversal is given.
Can anyone suggest me any algorithm for this ?
P.S: Is there any way to sketch the tree itself from the in-order result ?
Solution
You can't do that. Your example might represent multiple trees, for example :
E D
\ / \
D E B
\ \
B A
\ \
A G ...
\ \
G F
\ \
F G
\ \
H C
\
C
You need at least two orders to reconstruct the tree, and you can only give an order when you have the tree at hand.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow