## Binary Search Tree Properties

The keys in a binary search tree are always stored in such a way to
satisfy the binary search tree property:

"Let x be a node in a binary search tree. If y is a node in the left
subtree of x, then value[y]<=value[x]. If y is a node in the right
subtree of x, then value[x]<=value[y]."
Thus, in Figure 1.2 a, the value of the root is 5, the values 2, 3, and 4
in its left subtree are no larger than 5, and the values 7 and 8 in its
right subtree are no smaller than 5. The same property holds for every node
in the tree. For example, the value 3 in the Figure 1.2 b is no smaller
than the value 2 in its left subtree and no larger than the value 5 in
its right subtree.

Figure 1.2 Examples of Binary Trees

Previous Page

Next Page

Return to Main Page