Consider the following Inorder and Preorder traversal of a tree Inorder – D B…

Solution:

Given,

• Inorder: D B E F A G H C

• Preorder: A B D E F C G H

From the preorder traversal, the first node is the root.

Root = A

Splitting the inorder traversal about A:

• Left subtree: D B E F

• Right subtree: G H C

Left Subtree

Preorder: B D E F

• Root = B

• Inorder left of B = D

• Inorder right of B = E F

Thus:

• Left child of B = D

• Right child of B = E

• Right child of E = F

Right Subtree

Preorder: C G H

• Root = C

• Inorder left of C = G H

Thus:

• Left child of C = G

• Right child of G = H

The tree is:

        A
      /   \
     B     C
    / \   /
   D   E G
        \  \
         F  H

Now perform Postorder Traversal (Left → Right → Root):

• Left subtree of A: D F E B

• Right subtree of A: H G C

• Root: A

Therefore, the Postorder Traversal is:

D F E B H G C A

Answer: D F E B H G C A