TAOCP 2.3.1 Exercise 10
The stack grows only in step `T3`, where the current value of `P` is pushed onto `A` and then `P` is replaced by `LLINK(P)`.
Section 2.3.1: Traversing Binary Trees
Exercise 10. [20] What is the largest number of entries that can be in the stack at once, during the execution of Algorithm T, if the binary tree has n nodes? (The answer to this question is very important for storage allocation, if the stack is being stored consecutively.)
Verified: no
Solve time: 40s
Solution
The stack grows only in step T3, where the current value of P is pushed onto A and then P is replaced by LLINK(P). Therefore the number of entries in the stack at any moment is exactly the number of ancestors whose left subtrees are currently being traversed, together with the current node whose left link is about to be followed.
Suppose the stack contains $k$ entries. Then these entries correspond to a sequence of distinct nodes
$$ P_1,\ P_2,\ \ldots,\ P_k $$
such that
$$ P_{i+1}=LLINK(P_i)\qquad (1\le i<k). $$
Indeed, each push occurs immediately before moving from a node to its left child, and no pop can occur until the traversal reaches a null left link. Hence the stack contents form a simple downward chain of left links in the tree.
Since the tree contains only $n$ nodes, such a chain can contain at most $n$ distinct nodes. Therefore
$$ k\le n. $$
Thus the stack can never contain more than $n$ entries.
It remains to show that this bound can actually be attained. Consider the binary tree consisting of a chain of $n$ nodes, each node having a left child and no right child:
$$ P_1 \to P_2 \to \cdots \to P_n, $$
where
$$ LLINK(P_i)=P_{i+1}\quad (1\le i<n), \qquad LLINK(P_n)=\Lambda. $$
Starting with P = P_1, Algorithm T executes step T3 successively on
$$ P_1,\ P_2,\ \ldots,\ P_n. $$
After the push of $P_n$, the stack contains
$$ P_1,\ P_2,\ \ldots,\ P_n, $$
which is exactly $n$ entries. Only afterward does the algorithm encounter P = \Lambda and begin removing entries from the stack.
Hence a stack size of $n$ is achievable, and no larger size is possible.
Therefore the largest number of entries that can be in the stack at once is
$$ \boxed{n}. $$