Question

Consider 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:

1. + – 1 6 7 * 2 ^ 5 – 3 4 *
2. – + 1 * 6 7 ^ 2 – 5 * 3 4
3. – + 1 * 7 6 ^ 2 – 5 * 4 3
4. 1 7 6 * + 2 5 4 3 * – ^ –

Answer 1

Correct Answer - Option 3 : – + 1 * 7 6 ^ 2 – 5 * 4 3

In case of reverse polish notation, we follow the:

1) visit left subtree

2) visit right subtree

3) visit root

New order strategy is given as:

1) visit root

2) visit right subtree

3) visit left subtree

It is the reverse of reverse- polish notation.

So, for finding the new order traversal of given reverse polish notation just reverse that:

Reverse polish traversal: 3 4 * 5 – 2 ^ 6 7 * 1 + -

New order traversal:  – + 1 * 7 6 ^ 2 – 5 * 4 3

Alternate solution:

Convert the given reverse polish notation in IN- order

3 4 * 5 – 2 ^ 6 7 * 1 + -

(3 * 4) 5 – 2 ^ 6 7 * 1 + -

((3*4) - 5) 2 ^ 6 7 * 1 + -

(((3*4) - 5)^ 2) 6 7 * 1 + -

(((3*4) - 5)^ 2) (6 * 7) 1 + -

(((3*4) - 5)^ 2) ((6 * 7) + 1)

(((3*4) - 5)^ 2) - ((6 * 7) + 1)

Now, from this inorder traversal, find the new order traversal;

(((3*4) - 5)^ 2) - ((6 * 7) + 1)

- ((6 * 7) + 1) (((3*4) - 5)^ 2)

- + 1 (6 * 7) (((3*4) - 5)^ 2)

- + 1 * 7 6 (((3*4) - 5)^ 2)

- + 1 * 7 6 ^ 2 ((3*4) - 5)

- + 1 * 7 6 ^ 2 - 5 (3*4)

- + 1 * 7 6 ^ 2 - 5 * 4 3

Hence option 3 is correct.