GATE CSE 2014 Set 2 | Question: 39

Question

Consider the expression tree shown. Each leaf represents a numerical value, which can either be $0$ or $1$. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___. 

Comments

what is the minimum possible value of the same expression tree??

---

$\text{Minimum value will be -2}$

---

can you please recheck the answer,i was getting -3 as the minimum value.pls kindly check once again for me and if it is still -2 then pls post the logic here.

---

@Sai eswar How are you getting $-3$ as min value? It will be $-1-1 = -2$

Answer 1

consider the leaves as any variable, let-Y

now use bottom up parsing method and traverse from  top to down and left to right and evaluate the expression in such a manner so that it will give maximum output. here it is :

[(Y+Y)-(Y-Y)]+[(Y-Y)+(Y+Y)] then select the values such that it will give you maximum throughput.

here values are 1  1 0 1 1 0 1 1      ,

so if you will put these values respectively in above expression you will get maximum output:  6

Answer 2

lets number the nodes from left to right as a,b,c,d,e,f,,g,h, respectively now the expression tree reduces to ((a+b)-(c-d))+((e-f)+(g+h))now we can easily see the possible values of variables to get the maximum value. here a+b so we can take a=b=1 and then -(c-d) so we would like to get negative value from c-d so that it becomes positive  and add to a+b value and so on...

Answer 3

answer - 5

for addition operation we have to maximize operands

for subtraction operation we have to minimize minuend

use these values to maximize value of expression

leftmost leaves = (1,1)

second leftmost leaves = (0, 0)

third left most leaves = (1, 0)

rightmost leaves = (1, 1)