Use the empty reference as the base case: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.
def printInorder(root: Tree): Unit = {
if (root != null) {
printInorder(root.left)
println(root.datum)
printInorder(root.right)
}
} Articles by others on the same topic
There are currently no matching articles.