Chris Stover writes: "It is not enough
to specify that (left child) < node < (right child) for every node in the
BST. The stronger property that max(left subtree) < node < min(right
subtree) is required. Without this stronger property, the "bst-traverse"
function in figure 4.8 does not necessarily list elements in ascending
order as claimed on page 75. (Example: a tree with root node 1 having a
single right child 2 which has a single left child 0.) Fortunately, your
"bst-insert" function in figure 4.5 preserves the correct BST property.
On the other hand, the correct BST property is not preserved in all cases
by the "bst-remove" function given in figure 4.6. A deleted internal node
needs to be replaced either by the maximal node in the left subtree or by
the minimal node in the right subtree, and your function does not do this."
Keke (surname unknown) gives an example:
> (setf nums nil)
> (dolist (x '(5 8 4 2 1 9 6 7 3))
(setf nums (bst-insert x nums #'<)))
> (setf nums (bst-remove 5 nums #'<))
> (bst-traverse #'princ nums)