Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



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$


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...