The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+11 votes

Best 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

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.

+3

check this @sutanay3

for clarity image https://drive.google.com/open?id=188C6_9ckbY637fKagbg76fUKS-fxpqNv

+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$

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$

+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

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

+1 vote

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

0 votes

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

0 votes

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

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 586
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,129 questions

53,252 answers

184,785 comments

70,505 users