Question

Consider the following New-order startegy for traversing a binary tree.

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 7 6 * + 2 5 4 3 * - ^ -
• B. + - 1 6 7 * 2 ^ 5 - 3 4 *
• C. - + 1 * 6 7 ^ 2 - 5 * 3 4
• D. - + 1 * 7 6 ^ 2 - 5 * 4 3

Answer 1

The correct option is D - + 1 * 7 6 ^ 2 - 5 * 4 3

Reverse polish expression is another name for postfix notation. Since postfix notation is similar to postorder (LEFT, RIGHT, ROOT) and new order strategy is (ROOT, RIGHT, LEFT), both are reversals of each other.
Hence option (c) is the correct answer.