Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 4 / a / Solution

Treat a null reference as the empty binary tree and perform the visit before descending:By structural induction, the empty binary tree produces the empty output. A nonempty binary tree prints its root label, then the complete preorder traversal of the left subtree, then that of the right subtree. These are exactly the required output positions. The recursion terminates on a finite binary tree because each recursive call has strictly fewer vertices. For the three-node example, the output order is $2,1,3$. The time complexity is linear in the number of vertices, with call stack depth bounded by the height of a binary tree plus a constant.