Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a$, $b$, $c$, $d$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

We can determine the minimum number of registers required using the Ershov Numbers (Sethi-Ullman algorithm) for expression trees on a load-store architecture:

1. Leaves (operands in memory): Loading any variable $a, b, c, d, e$ from memory into a register requires $1$ register. Thus, Ershov number for each leaf is $1$.

2. Node $(c + d)$: Both children require $1$ register. Since they are equal, the cost is:

   $$R(c + d) = 1 + 1 = 2$$

3. Node $(e - (c + d))$:

   • Left child ($e$) has weight $1$.

   • Right child ($(c + d)$) has weight $2$.

   Evaluating the right child first requires $2$ registers (result held in $1$ register), and then evaluating the left child requires $1$ register. Since the right child requires strictly more registers than the left, the cost is:

   $$R(e - (c + d)) = \max(2, 1 + 1) = 2$$

4. Node $(a - b)$: Both leaves require $1$ register, so:

   $$R(a - b) = 1 + 1 = 2$$

5. Root Node $( (a - b) + (e - (c + d)) )$: Both left and right subtrees require $2$ registers. When both children have the same weight $k$, the parent requires $k + 1$ registers:

   $$R(\text{root}) = 2 + 1 = 3$$

Thus, a minimum of 3 registers are required.

Hence, the correct option is (D).