The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
2.7k 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 Veteran (49.5k points)
edited by | 2.7k views

4 Answers

+39 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.2k points)
edited by
+56 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.6k points)

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

awesome!!

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

Great observation

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

+14 votes

Another way to go => Answer C

1. Convert Postfix to Infix

2. Create expression tree.

3. Run the code !

answered by Veteran (49.5k points)
+1 vote

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 Veteran (11.2k 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

33,700 questions
40,250 answers
114,331 comments
38,858 users