2.3k 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 possible value of the expression represented by the tree is ___. edited | 2.3k views
0
what is the minimum possible value of the same expression tree??
0
$\text{Minimum value will be -2}$ $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

by Boss (10.8k points)
selected by
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$
by (115 points)
edited by

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 tree by Loyal (9.9k points)
0
Can someone give me a good approach of how to think about such questions.It seems difficult to derive the correct answer in exam time.
0
Something is weird with the explanation.
+4

check this @sutanay3 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

by Active (2.9k points)
+1 vote

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

by (27 points)
+1 vote
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...
by Active (1.9k points)

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)
by Loyal (8.6k points)