GATE CS 2007 Q39 — Trees

To find the postorder traversal, we first reconstruct the unique binary tree using the given preorder and inorder traversals.

Given:

• Inorder: $\text{d \; b \; e \; a \; f \; c \; g}$
• Preorder: $\text{a \; b \; d \; e \; c \; f \; g}$

Step 1: Reconstruct the Binary Tree

1. The first element in the preorder traversal is the root of the tree. Thus, a is the root.
2. Locating a in the inorder traversal splits the tree into:
   • Left subtree elements: $\{\text{d, b, e}\}$
   • Right subtree elements: $\{\text{f, c, g}\}$
3. For the left subtree $\{\text{d, b, e}\}$:
   • Its preorder sequence is $\text{b \; d \; e}$, so b is the root of this subtree.
   • In the inorder sequence $\text{d \; b \; e}$, d is to the left of b, and e is to the right. Thus, d is the left child and e is the right child of b.
4. For the right subtree $\{\text{f, c, g}\}$:
   • Its preorder sequence is $\text{c \; f \; g}$, so c is the root of this subtree.
   • In the inorder sequence $\text{f \; c \; g}$, f is to the left of c, and g is to the right. Thus, f is the left child and g is the right child of c.

The reconstructed binary tree is:

       a
      / \
     b   c
    / \ / \
   d  e f  g

Step 2: Find the Postorder Traversal

Postorder traversal follows the Left $\rightarrow$ Right $\rightarrow$ Root policy:

• Postorder of left subtree (rooted at b): $\text{d \; e \; b}$
• Postorder of right subtree (rooted at c): $\text{f \; g \; c}$
• Postorder of the entire tree: $\text{d \; e \; b \; f \; g \; c \; a}$

This matches Option A.