edited by
9,346 views
44 votes
44 votes

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 ___. 

edited by

7 Answers

Best answer
29 votes
29 votes

$A = B + C$

For $A$ to be maximum, both $B$ and $C$ should be maximum

$B = D - E$

For $B$ to be maximum, $D$ should be maximum and $E$ should be minimum

$C = F + G$

For $C$ to be maximum, both $F$ and $G$ should be maximum

The maximum value of $D$ is $2\;( 1 + 1 = 2 )$

The minimum  value of $E$ is $-1 \;( 0 - 1 = -1 )$

The maximum value of $F$ is $1 \;( 1 - 0 = 1 )$

The maximum value of $G$ is $2 \;( 1 + 1 = 2 )$

$B = 2 - ( -1 ) = 2 + 1 = 3$

$C = 1 + 2 = 3$

$A = B + C = 3 + 3 = 6$

$6$  is the answer 

selected by
19 votes
19 votes
ans is $6$

at left  leafs

$+$   $---> (1,1)=2$         intermediate $+ ---->  2-(-1)=3  $  

$-$   $---->(0,1)=-1$

at right leafs

$-$  minus $---->(1,0)=1$       intermediate   $+$    $----> 1+2=3$

$+$     $---->(1,1)=2$

 

at root   $+ ---> 3+3=6$
edited by
12 votes
12 votes

An Expression Tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand so for example expression tree for 3 + ((5+9)*2) would be:. Below diagram shows values to pick to get the maximum value in expresison treeGATECS2014Q38

5 votes
5 votes
lets say every leaf denoted by x

then expression look like this (x + x)-(x - x)+(x - x)+(x +x )

                                        =  1     1  0   1     1   0    1   1 (this combination will give maxiumum value)

                                         = (1 + 1)-(0-1) + (1-0) + (1+1)=6

So answer is 6
Answer:

Related questions

4 votes
4 votes
1 answer
3
Rohan Mundhey asked Oct 2, 2016
312 views
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...