3.5k views

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 \wedge 5 \ - \ 3 \ 4 \ *$
2. $- + 1 * 6 \ 7 \wedge 2 - 5 * 3 \ 4$
3. $- + 1 * 7 \ 6 \wedge 2 \ - \ 5 \ * \ 4 \ 3$
4. $1 \ 7 \ 6 * + \ 2 \ 5 \ 4 \ 3 \ * \ - \wedge -$
edited | 3.5k views

Expression given in reverse polish notation (i,e in Post-order)

convert first it into In-order

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

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

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

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

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

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

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

so Inorder expression in $((((3*4)-5) \wedge 2)-((6*7)+1))$

New-Order traversal is as by ROOT RIGHT LEFT

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

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

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

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

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

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

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

option C is correct
edited by
It is quite simple actually.

Postorder: left, right, root

Neworder: Root, right, left

(left, right, root) and (Root, right, left) are reverse of each other, right ?

So, these two traversals will be exact reverse of each other! Option (c)!
+2

Hi @Ashish Deshmukh ji very good answer. If someone is thinking about proof then think proof via technique like induction.

+2
awesome!!

Logical thinking is very important in CSE when compared to mathematical/bookish knowledge.Your solution is very logical
+3

Great observation

CS:Common sense(Another Full form of Computer Science)

Another way to go => Answer C

1. Convert Postfix to Infix

2. Create expression tree.

3. Run the code !

Reverse polish notation is postfix notation ,so we have postfix form expression

Firstly we have to convert POSTFIX -> INFIX

Which can be converted as given in my reference answer https://gateoverflow.in/8408/gate2015-3_12

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

So new order is Root Right Left

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

-((*76)+1))(((*43)-5)^2)

-(+1*76)((-5*43)^2)

-+1*76^2-5*43

so option c is right

1
2