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 ___.
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
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 ( 1 + 1 = 2 )
The minimum value of E is ( 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
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
yes sir TRUE... working on it :). But this...