= Solution
In a <preorder traversal>, visit the root before the left <subtree>, then visit the right <subtree>. The `NIL` test prevents visiting or dereferencing an empty <binary tree>:
``
PROCEDURE preorder(t : node);
BEGIN
IF t # NIL THEN
visit(t);
preorder(t.left);
preorder(t.right)
END
END preorder;
``
<Structural induction> proves correctness. The empty <binary tree> has nothing to visit. For a nonempty root, `visit(t)` comes first; by the <induction hypothesis>, each recursive call visits exactly its own <subtree> in <preorder traversal> order, and the left call finishes before the right begins. Each recursive call receives a strictly smaller finite <tree>, proving termination. Assuming `visit` neither changes the child links nor fails to return, the procedure therefore realizes
$$
\boxed{\operatorname{preorder}(t)=t,\ \operatorname{preorder}(t.left),\ \operatorname{preorder}(t.right).}
$$
For $m$ nodes, overhead is $\Theta(m+1)$ and <recursion> depth is $O(h+1)$ for height $h$, in addition to the cost of `visit`. The claim presumes an actual <binary tree>; cycles or shared nodes in an arbitrary pointer <graph> need additional handling if each object is to be visited exactly once.
Back to article page
