Project ForgeConsider the following New-order strategy for traversing a binary tree: • Visit the root; • Visit the right subtree using New-order; • Visit the left subtree using New-order;
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:
- A+ - 1 6 7 * 2 ^ 5 - 3 4 *
- B- + 1 * 6 7 ^ 2 - 5 * 3 4
- - + 1 * 7 6 ^ 2 - 5 * 4 3
- D1 7 6 * + 2 5 4 3 * - ^ -
Explanation
Building the expression tree from the postfix string via the standard stack method gives root '-' with left subtree T3=((3*4)-5)^2 and right subtree T5=(6*7)+1. Applying New-order (root, then right subtree recursively, then left subtree recursively): root '-'; then T5's New-order gives '+','1','*','7','6' (root '+', right leaf '1', then left subtree '*' with its own right '7' then left '6'); then T3's New-order gives '^','2','-','5','*','4','3' (root '^', right leaf '2', then left subtree '-' with right leaf '5' then left subtree '*' giving '4','3'). Concatenating: - + 1 * 7 6 ^ 2 - 5 * 4 3 — exactly option (C).
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.