 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)
NIL
> (dolist (x '(5 8 4 2 1 9 6 7 3))
(setf nums (bst-insert x nums #'<)))
NIL
> (setf nums (bst-remove 5 nums #'<))
#<4>
> (bst-traverse #'princ nums)
13246789
|