Tree Traversal

Tree traversal is the algorithmic process of visiting every node in a tree data structure exactly once, in some defined order. Though the concept is elementary — depth-first search, breadth-first search, and their variants — the choice of traversal order determines what computations are local and what require global state. A pre-order traversal visits a node before its children, making it natural for copying trees or evaluating prefix expressions. A post-order traversal visits children before their parent, making it natural for computing sizes or freeing memory. An in-order traversal, defined for binary trees, visits left subtree, root, right subtree, recovering the sorted order of a binary search tree.

The significance of tree traversal extends far beyond data structures. A compiler's semantic analyzer is a tree traversal with a side table. A DOM update in a web browser is a traversal of the HTML tree. A proof assistant's tactic engine traverses the goal tree. In each case, the traversal order is not an implementation detail but a commitment about which information flows upward (from children to parent) and which flows downward (from parent to children, or from siblings through a shared context).

Tree traversal is also the canonical setting for understanding recursion. Every recursive tree algorithm is a traversal in disguise, and the call stack itself is a traversal state implicitly maintained by the runtime. The duality between explicit stack-based iteration and implicit recursion reveals that traversal is not merely about trees — it is about the sequencing of computations over hierarchical structures, whether those structures are data in memory or goals in a proof.