PRE ORDER POST ORDER IN ORDER

The post order traversal of a binary tree is
DEBFCA. Find out the pre- order traversal.
(A) ABFCDE
(B) ADBFEC
(C) ABDECF
(D) None of the above
Ans:-C
Explanation:-
A binary tree is a data structure which has at
most two child nodes. A binary tree can be
traversed in three ways. Inorder, preorder and
postorder. The three methods of traversal can
be explained this way.
TYPE FIRST SECOND THIRD
Inorder L - Left Ro - Root R - Right
Preorder Ro - Root L - Left R - Right
Postorder L - Left R - Right Ro - Root
Left will always be followed by right. But Root
would be either in the front or in the middle
or at the last depending on whether it is pre,
in or postorder traversal. So given a post order
traversal of a binary tree, we can know the
root first. In the question, the post order
traversal is given as DEBFCA. Since Root is the
last node to be traversed in a post order
traversal we know one thing for sure. A is the
root.
Next, we are left with only DEBFC. Here some
of the nodes belong to the left side of the
binary tree and some belong to the right side.
How many nodes belong to the left and how
many belong to the right. Since left side of the
binary tree is considered first, and since every
node is expected to have at most two child,
DEB will be the left side of the binary tree and
FC would be the right.
Now, we know that FC is in the right side of
the binary tree. Again the last node would be
the root of the sub tree and F its left side.
Next we come to the left side of the binary
tree and it is DEB. Again B would be the root
of the sub tree. D and E are its left and right
side respectively. So the binary tree would
look something like this given below.
After constructing the binary tree, writing the
preorder traversal is very simple. In preorder
traversal root comes first. Since A is the root,
A would appear first. Following Root would be
the Left and Right sub tree and so the left
subtree would be BDE. Again B would be the
root of the left sub tree followed by D and E
which are the left and right child respectively.
SO the preorder traversal till now would be
ABDE. Last comes the Right sub tree. Here
again C would be the root of the right sub tree
followed by C its left child. So the entire
preorder traversal of the tree would be
ABDECF. So option C is the right answer.