The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
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 -$ 
asked in DS by Boss (43.2k points)
edited by | 3.5k views

4 Answers

+45 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
+78 votes
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)!
answered by Active (1.5k points)
+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)

+19 votes

Another way to go => Answer C

1. Convert Postfix to Infix

2. Create expression tree.

3. Run the code !

answered by Boss (43.2k points)
+2 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 Loyal (7.3k points)
Answer:

Related questions



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

44,074 questions
49,595 answers
162,959 comments
65,791 users