= Solution
Use the empty reference as the <base case>:
``
def printInorder(root: Tree): Unit = {
if (root != null) {
printInorder(root.left)
println(root.datum)
printInorder(root.right)
}
}
``
<Induction> on the tree proves the order: the first <recursive call> prints exactly the left <subtree>, then the procedure prints the root, then the final call prints exactly the right <subtree>. A finite acyclic tree supplies decreasing proper <subtrees>, so the <recursion> terminates. The traversal is valid for arbitrary <integer> labels; sorted output would additionally require a <binary search tree> <invariant>.
Back to article page
