The GATE Grind

GATE 2014 CS (CS2) – Question 49

Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Numerical answer

Each leaf of the shown expression tree independently has value 0 or 1. Find the maximum value of the expression over all leaf assignments.

Diagram for GATE 2014 CS (CS2) question 49

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 6 to 6

Explanation

Write the leaves left-to-right as a,…,h. The expression expands to a+b−c+d+e−f+g+h. Set the six positive-coefficient leaves to1 and c,f to0. The maximum is **6**; each leaf is independently selectable.