Consider the expression tree shown. Each leaf represents a numerical value,…
2014
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 ___.
Attempted by 43 students.
Show answer & explanation
Correct answer: 6
Key idea: expand subtractions and collect the leaf variables with their signs.
Label the eight leaves from left to right as a, b, c, d, e, f, g, h (each is 0 or 1).
Left subtree: the left child is (a + b) and the right child is (c - d), so the left subtree equals (a + b) - (c - d) = a + b - c + d.
Right subtree: the left child is (e - f) and the right child is (g + h), so the right subtree equals (e - f) + (g + h) = e - f + g + h.
Whole expression (root +): sum the two subtrees to get a + b - c + d + e - f + g + h.
To maximize this with each variable 0 or 1, set every variable with a positive coefficient to 1 and every variable with a negative coefficient to 0. The positively signed variables are a, b, d, e, g, h (six variables). The negatively signed variables are c and f.
Therefore the maximum possible value is 6.
A video solution is available for this question — log in and enroll to watch it.