The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.9k 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 ^ 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 * - ^ -

 

 

 

asked in DS by Veteran (46.8k points)
edited by | 1.9k views

4 Answers

+29 votes
Best answer
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
answered by Veteran (55.3k points)
edited by
+38 votes

Its 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) ! Answer in few seconds, basic concept ! Observation !

 

answered by Active (1.5k points)

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

+12 votes

Another way to go => Answer C

1. Convert Postfix to Infix

2. Create expression tree.

3. Run the code !

answered by Veteran (46.8k points)
0 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 

answered by Boss (7.3k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,158 questions
36,985 answers
92,168 comments
34,824 users