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.