2,028 views
2 votes
2 votes

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, +, –

1 Answer

Best answer
6 votes
6 votes

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 +  -

 

selected by

Related questions

2 votes
2 votes
2 answers
1
4 votes
4 votes
1 answer
2
Shashank Chavan asked Jan 18, 2016
11,129 views
What's the difference between Binary tree height, level and depth? Sometimes it's confusing!Does there definition change according to question also, if mentioned?
0 votes
0 votes
5 answers
4
radha gogia asked Sep 30, 2015
1,607 views
If I am given an array $X$ of $n$ distinct integers which is interpreted as a complete binary tree, so if the parent is at index $i$, then it's left child would be at ind...