# GATE2014-2-39

4.1k 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
0
what is the minimum possible value of the same expression tree??
1
$\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

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$

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

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

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

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

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)

## Related questions

1
11.9k views
For a C program accessing $\mathbf{X[i] [j] [k]}$, the following intermediate code is generated by a compiler. Assume that the size of an integer is $32$ bits and the size of a character is $8$ bits. t0 = i ∗ 1024 t1 = j ∗ 32 t2 = k ∗ 4 t3 = t1 + t0 t4 = t3 + t2 t5 = X[t4] ... $\mathbf{X}$ is declared as "char $\mathbf{X[4] [32] [8]}$ . $\mathbf{X}$ is declared as "char $\mathbf{X[32] [16] [2]}$ .
Consider the grammar defined by the following production rules, with two operators $∗$ and $+$ $S\:\to\:T∗P$ $T\:\to\:U\mid T∗U$ $P\:\to\:Q+P\mid Q$ $Q\:\to Id$ $U\:\to Id$ Which one of the following is TRUE? $+$ is left associative, while $∗$ is right associative $+$ is right associative, while $∗$ is left associative Both $+$ and $∗$ are right associative Both $+$ and $∗$ are left associative
Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, ... be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________