= Solution
Let $d_e=\operatorname{depth}(e)$ and $d_f=\operatorname{depth}(f)$ measure the extra operand <stack> space required from the current base, with each evaluation leaving one result. Evaluating $e$ first uses $d_e$ slots. Its result occupies one slot while evaluating $f$, so that stage uses $1+d_f$ slots. The final `add` reduces two slots to one. Thus
$$
\boxed{d_{e\text{ first}}=\max(d_e,1+d_f),\qquad d_{f\text{ first}}=\max(d_f,1+d_e).}
$$
By <commutativity> of <addition>, choose the smaller of these two bounds. Evaluate the child of larger depth first. The optimum recurrence on a <binary expression tree> is
$$
\boxed{\operatorname{depth}(e+f)=\begin{cases}\max(d_e,d_f),&d_e\ne d_f,\\d_e+1,&d_e=d_f.\end{cases}}
$$
Assign depth one to a literal or a simple already-addressable value, and compute the child depths recursively. If $d_e>d_f$, the depths are <integers>, so $d_e\geq1+d_f$; evaluating $e$ first therefore attains $d_e$, while reversing the order needs $d_e+1$. If the depths are equal, whichever child goes second needs the extra retained-result slot. These lower bounds prove the recurrence is optimal for evaluating each child subtree without interleaving or spilling. Apply it at every node to minimize peak operand <stack> occupancy for the given <binary expression tree>; this is <optimal stack evaluation of a binary expression tree>.
This changes child evaluation order, not the parenthesization. For example, a chain-shaped <binary expression tree> can have depth two, whereas a balanced tree of eight leaves has depth four under this model. The reordering assumes expressions have no order-sensitive <side effects> or observable exceptions. Reassociating <floating-point addition> would require additional care because it can change <floating-point rounding>.
Back to article page
