= Explicit-stack depth-first tree traversal
An <explicit-stack depth-first tree traversal> stores pending subtree roots instead of suspended recursive calls. In a <binary tree>, visit the current node, defer its nonempty right child on a <stack>, and continue with its left child; pop when the current subtree is empty. The unvisited subtrees remain disjoint and, together with the visited nodes, partition the original tree. This <loop invariant> proves that accumulating each visited label gives the tree sum. At most one right sibling per ancestor is pending, so auxiliary storage is $O(d)$ for depth $d$ and running time is $\Theta(N)$ for $N$ nodes. Unlike a full recursive <stack frame>, a pending entry need contain only a subtree <pointer>.
Back to article page
