4
Consider the traversal of a tree
Preorder $\to ABCEIFJDGHKL$
Inorder $\to EICFJBGDKHLA$
Which of the following is correct post order traversal?
Solution
Given,
Preorder traversal:
$ABCEIFJDGHKL$
Inorder traversal:
$EICFJBGDKHLA$
In preorder traversal, the first element is always the root.
So, root is:
$A$
In inorder traversal, $A$ is at the end.
So, all remaining nodes are in the left subtree of $A$.
Now, after $A$, the next root in preorder is:
$B$
In inorder traversal:
$EICFJBGDKHL$
Here, nodes before $B$ are in left subtree of $B$:
$EICFJ$
Nodes after $B$ are in right subtree of $B$:
$GDKHL$
Now solve left subtree of $B$.
Preorder part is:
$CEIFJ$
Root is $C$.
Inorder part is:
$EICFJ$
Left of $C$ is $EI$ and right of $C$ is $FJ$.
For $EI$, root is $E$, so postorder is:
$IE$
For $FJ$, root is $F$, so postorder is:
$JF$
So, postorder of subtree rooted at $C$ is:
$IEJFC$
Now solve right subtree of $B$.
Preorder part is:
$DGHKL$
Root is $D$.
Inorder part is:
$GDKHL$
Left of $D$ is $G$ and right of $D$ is $KHL$.
So, left postorder is:
$G$
For right part $KHL$, root is $H$.
Left of $H$ is $K$ and right of $H$ is $L$.
So, postorder of subtree rooted at $H$ is:
$KLH$
Thus, postorder of subtree rooted at $D$ is:
$GKLHD$
Now, postorder of subtree rooted at $B$ is:
$IEJFCGKLHDB$
Finally, root $A$ comes at the end.
So, final postorder traversal is:
$IEJFCGKLHDBA$