The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
303 views

Consider the following last level order strategy for traversing a binary tree:
• Visit right sub tree using last level order.
• Visit left sub tree using last level order.
• Visit root.
Assume ↑ is power operator and it has the highest precedence and follows right associativity. The last level order traversal of expression tree corresponding to the given postorder traversal is

7 7 1 ↑ 7 1 * / + 7−

  1.  7, 1, 7, *, 1, 7, ↑, 7, /, +, –
  2.  7, –, 1, *, 7, /, 1, ↑, 7, +, 7
  3.  7, 1, 7, *, 1, 7, ↑, /, 7, +, –
  4.  7, 7, 1, *, 1, 7, ↑, /, 7, +, –
in DS by Active (1.9k points) | 303 views
0
option c, isthe asnwer

1 Answer

+3 votes
Best answer

expression trees post-order gives us postfix notation.

expression trees pre-order gives us prefix notation.

if   7 7 1 ↑ 7 1 * / + 7 −   is post order, then    -   +   7   /   ↑  7  1  *  7 1 7  is it's pre order.

last level order strategy on a Tree ( not standard as per given rule ) ====> print Right , Print Left , Print DATA.

What is our well known strategy of preorder ==> Print Data, Print Left, Print Right

this is exactly reverse of the last level strategy post-order !

Post-order of  last level strategy  on the Tree = Reverse ( Well known Pre-order on the Tree )

= Reverse (  -   +   7   /   ↑  7  1  *  7 1 7 ) = 7 1 7 * 1 7 ↑ /  7 +  -

 

by Veteran (61.9k points)
selected by
0

Thanks @Shaik Masthan! Seems good to me.?

0
how u convert postorder to preorder ..is there any shortcut?
0
Shaik Masthan can you please show expression tree for the above problem??
+2

by givien post order, the expression tree like :

By knowing the tree, on applying specified traversal order, you can get option C as answer

0

if   7 7 1 ↑ 7 1 * / + 7 −   is post order, then    -   +   7   /   ↑  7  1  *  7 1 7  is it's pre order.

how did u get this?? @Shaik Masthan sir

0
did you mean, how i directly did it ?
0
yes,

because in bst, everyone can write directly but how u wrote directly in binary tree?
+1
on the previous image posted by me, i written first expression to be evaluated, second expression to be evaluated, etc...

in those, operator is at last ===> post order,

So, keep it in front of the operands ==> preorder.
0

Thanks a lot @Shaik Masthan

Related questions

+1 vote
2 answers
1
+1 vote
0 answers
7
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
49,807 questions
54,727 answers
189,302 comments
79,845 users