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 ___.
$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
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
check this @sutanay3
for clarity image https://drive.google.com/open?id=188C6_9ckbY637fKagbg76fUKS-fxpqNv
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