GATE CS 2016 Set 2 Q36 — Trees

To find the New-order traversal, we first construct the expression tree from the given reverse polish (postfix) expression:

$$\text{Postfix: } 3 \ 4 \ * \ 5 \ - \ 2 \ \wedge \ 6 \ 7 \ * \ 1 \ + \ -$$

Evaluating the postfix expression yields the following binary expression tree:

• The root is the final operator: -
• The left subtree $T_L$ represents: $(((3 * 4) - 5) \wedge 2)$
• The right subtree $T_R$ represents: $((6 * 7) + 1)$

The New-order traversal scheme is defined as: Root $\to$ Right Subtree $\to$ Left Subtree.

Applying this recursively:

1. At the Root: $$\text{New-order}(T) = [-] \cdot \text{New-order}(T_R) \cdot \text{New-order}(T_L)$$
2. For the Right Subtree $T_R$ (root +, left * (6, 7), right 1): $$\text{New-order}(T_R) = [+] \cdot [1] \cdot \text{New-order}(6 * 7)$$ $$\text{New-order}(6 * 7) = [*] \cdot [7] \cdot [6]$$ $$\text{New-order}(T_R) = + \ 1 \ * \ 7 \ 6$$
3. For the Left Subtree $T_L$ (root ^, left - (T_1, 5), right 2): $$\text{New-order}(T_L) = [\wedge] \cdot [2] \cdot \text{New-order}(T_1 - 5)$$ $$\text{New-order}(T_1 - 5) = [-] \cdot [5] \cdot \text{New-order}(3 * 4)$$ $$\text{New-order}(3 * 4) = [*] \cdot [4] \cdot [3]$$ $$\text{New-order}(T_L) = \wedge \ 2 \ - \ 5 \ * \ 4 \ 3$$

Combining these results gives the complete traversal:

$$- \ + \ 1 \ * \ 7 \ 6 \ \wedge \ 2 \ - \ 5 \ * \ 4 \ 3$$

This matches Option C.