 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 realizesFor $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.