CSC 378 tutorial: The Binary Search Tree Property

Each node of a Binary Search Tree (BST) stores a piece of data, called the key . Each node has below it a left subtree and a right subtree. The topmost node is called the root and a node with no subtrees is called a leaf.

The most important property of a BST is that

for a node with key k , every key in the left subtree is less than k and every key in the right subtree is greater than k.

Example

In this tree, the root contains key 35, every key in the left subtree of the root is less than 35 (these are 11, 20, and 29), and every key in the right subtree is greater than 35 (these are 40, 43, 47, 50, 60, 65, and 72).

This property is true of every node in the tree. For example, the node containing key 50 has 40, 43, and 47 in its left subtree, and has 60, 65, and 72 in its right subtree.

If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

CSC 378 tutorial: The Binary Search Tree Property

Example

See also