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