GATE CS 1996 Q1.15 — Trees

The binary tree represented in the image has the following structure:

• Root: $a$
  • Left child: $b$
    • Left child: $c$ (which has a left child $g$)
    • Right child: $d$
  • Right child: $e$ (which has a left child $f$)

To find the post-order traversal (Left $\rightarrow$ Right $\rightarrow$ Root):

1. Left Subtree of $a$ (rooted at $b$):
   • Left subtree of $b$ (rooted at $c$): Visit left child $g$, then root $c$ $\rightarrow$ g, c
   • Right child of $b$: Visit $d$ $\rightarrow$ d
   • Visit root $b$ $\rightarrow$ b
   • Combined left subtree sequence: g, c, d, b
2. Right Subtree of $a$ (rooted at $e$):
   • Left child of $e$: Visit $f$ $\rightarrow$ f
   • Visit root $e$ $\rightarrow$ e
   • Combined right subtree sequence: f, e
3. Root node: Visit $a$ $\rightarrow$ a

Combining these steps, the complete post-order traversal sequence is: $g \; c \; d \; b \; f \; e \; a$.