edited by
16,577 views
65 votes
65 votes

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 by

6 Answers

3 votes
3 votes

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 

Answer:

Related questions

168 votes
168 votes
17 answers
1
Akash Kanase asked Feb 12, 2016
49,477 views
The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is _________.No...
73 votes
73 votes
5 answers
2