void inorder(tree t)
{
if(t == NULL)
return;
inorder(t->left);
printf(“%d “, t->val);
inorder(t->right);
}

It is particularly common to use an inorder traversal on a binary search tree because this will return values from the underlying set in order, according to the comparator that set up the binary search tree (hence the name).
To see why this is the case, note that if n is a node in a binary search tree, then everything in n ‘s left subtree is less than n, and everything in n ‘s right subtree is greater than or equal to n. Thus, if we visit the left subtree in order, using a recursive call, and then visit n, and then visit the right subtree in order, we have visited the entire subtree rooted at n in order. We can assume the recursive calls correctly visit the subtrees in order using the mathematical principle of structural induction. Traversing in reverse inorder similarly gives the values in decreasing order.

Advertisements