= Solution
Let $N$ be the number of nonempty nodes and $d$ the maximum number on a root-to-leaf path. Both listings take \b[$\Theta(N)$ time] on a unit-cost machine: each node is visited once and its three fields are read once. The recursive listing executes two child calls per nonempty node, including calls on empty children; there are $2N+1$ invocations in total. It saves and restores four words for every nonempty invocation. The iterative listing has one function frame, no recursive calls, and one push/pop pair per deferred nonempty right subtree. Thus it removes repeated call/return and frame-transfer overhead, although its extra loop tests also cost instructions. Exact cycle comparisons need a specified processor, memory timing and compiler; an optimizing compiler may alter either implementation.
For these particular <assembly language> listings, the recursive <call stack> uses $16d$ bytes above the caller's frame; empty calls allocate no additional frame. The iterative listing uses a fixed $128+16=144$ bytes, even for a shallow or empty tree. With $d\leq32$, the recursive maximum is 512 bytes, versus 144 bytes for this fixed-array iteration. If the promised depth of 32 instead counts edges, the recursive bound is $16\cdot33=528$ bytes; the same 32-word pending array still suffices. Conversely, for $d\leq8$ recursion uses at most 128 bytes and is smaller than the fixed array. When sized dynamically to depth, both approaches use $O(d)$ auxiliary storage, but their stored information differs: full suspended invocation state versus pending subtree roots. Therefore \b[recursion is not intrinsically always slower or larger]; the claim depends on generated code, tree shape and the choice to reserve a maximum-size explicit array.
Back to article page
