Optimal stack evaluation of a binary expression tree ($d(e\circ f)=\min \{\max (d(e),1+d(f)),\max (d(f),1+d(e))\}$)

Suppose each subtree of a binary expression tree is evaluated completely before its sibling, leaves one result on an operand stack, and is not spilled or interleaved. If the child depths are $p,q$, evaluating the first child needs $p$ slots and keeping its result while evaluating the second needs $1+q$. Reversing the order gives $\max (q,1+p)$. If either order preserves the expression's meaning, the minimum is $\max (p,q)$ when $p\ne q$ and $p+1$ when $p=q$. For example, if $p>q$, integrality gives $p\ge q+1$, so evaluating the deeper child first attains the lower bound $p$. If $p=q$, the second child needs its own $p$ slots plus one saved result regardless of order. Induction over the binary expression tree proves optimality in this evaluation model.

For a noncommutative operator, an instruction swapping the top two stack entries or a reverse-operand opcode permits the same ordering while preserving operand positions. Reordering still requires absence of order-sensitive side effects. Reassociation and interleaving are separate transformations and are not part of this optimality claim.