Binary search trees - Data Structures and Problem Solving Using Java - page 688

The binary search tree satisfies the search order property; that is, for
every node X in the tree, the values of all the keys in the left subtree are
smaller than the key in X and the values of all the keys in the right subtree are
larger than the key in X . The tree shown in Figure 19.1(a) is a binary search
tree, but the tree shown in Figure 19.1(b) is not because key 8 does not belong
in the left subtree of key 7. The binary search tree property implies that all the
items in the tree can be ordered consistently (indeed, an inorder traversal
yields the items in sorted order). This property also does not allow duplicate
items. We could easily allow duplicate keys; storing different items having
identical keys in a secondary structure is generally better. If these items are
exact duplicates, having one item and keeping a count of the number of dupli-
cates is best.

For any node in the
binary search tree,
all smaller keyed
nodes are in the
left subtree and all
larger keyed nodes
are in the right sub-
tree. Duplicates are
not allowed.

binary search tree order property
In a binary search tree, for every node X , all keys in X 's left subtree have smaller
values than the key in X , and all keys in X 's right subtree have larger values than
the key in X .

19.1.1 the operations

For the most part, the operations on a binary search tree are simple to visu-
alize. We can perform a find operation by starting at the root and then
repeatedly branching either left or right, depending on the result of a com-
parison. For instance, to find 5 in the binary search tree shown in
Figure 19.1(a), we start at 7 and go left. This takes us to 2, so we go right,
which takes us to 5. To look for 6, we follow the same path. At 5, we would
go right and encounter a null link and thus not find 6, as shown in
Figure 19.2(a). Figure 19.2(b) shows that 6 can be inserted at the point at
which the unsuccessful search terminated.
The binary search tree efficiently supports the findMin and findMax opera-
tions. To perform a findMin , we start at the root and repeatedly branch left as
long as there is a left child. The stopping point is the smallest element. The

A find operation is
performed by
repeatedly branch-
ing either left or
right, depending on
the result of a
comparison.

figure 19.1
Two binary trees: (a) a
search tree; (b) not a
search tree

7 7

2 9 2 9

1 5 1 5

3 3 8

(a) (b)