ISRO2017-50

Question

If the post order traversal gives ab -cd * + then the label of the nodes 1,2,3.. will be

• A. + , -, *, a,b,c,d
• B. a, -,b,+,c,*,d
• C. a,b,c,d,-,*,+
• D. -,a,b,+,*,c,d

Answer 1

PostOrder Traversal of the given tree gives the output: 4 5 2 6 7 3 1.

Comparing the output with a b - c d * + , and making one-to-one correspondence with 4 5 2 6 7 3 1 , we get

1 $\rightarrow$ +,

2 $\rightarrow$ - ,

3 $\rightarrow$ *,

4 $\rightarrow$ a,

5 $\rightarrow$ b,

6 $\rightarrow$ c,

7 $\rightarrow$ d,
 

which matches with option (A)

Comments

The correct infix expression of the given postorder is: $(a-b)+(c*d)$

Answer 2

In order will be (a-b)+(c*d)

now draw a traversal tree

Answer 3

First we draw a curve around the tree starting at the root, moving along the edges and terminate at the root.

Now for the post order traversing, we list the vertices last time the curve passes.

Here those vertices are in order 4>>5>>2>>6>>7>>3>>1...

Since 4=a, 5=b, 2=-, 6=c, 7=d, 3=*, 1=+

This gives A as the answer...