= Solution
Treat a null reference as the empty <binary tree> and perform the visit before descending:
``
def preorderRecursive(t: Tree): Unit = {
if (t != null) {
println(t.datum)
preorderRecursive(t.left)
preorderRecursive(t.right)
}
}
``
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, \b[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.
Back to article page
