A binary search tree is a binary tree that is either

empty or in which each node contains a key that

satisfies the following conditions:

1) All keys (if any) in the left subtree of the root

precede (are less than or equal to) the key of the

root.

2) The key in the root precedes (is less than) all keys

(if any) in its right subtree.

3) The left and right subtrees of the root are again

binary search trees.