GATE 2011 CS (CS1) – Question 46
Evaluate the shown expression tree on a load-store machine: memory holds a,b,c,d,e; binary operations use register operands and produce register results. No intermediate may be stored to memory. What is the minimum register count?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 3
Explanation
The expression is (a−b)+(e−(c+d)). A pair of leaves needs two registers; the right subtree needs two by evaluating c+d first and then loading e. Hold one subtree result while evaluating the other, requiring three. Two cannot retain one result while computing the other two-register subtree. Thus three, D.