Binary Search Trees

Binary search trees (or BST for short) are a special case of binary trees, which have an added constraint on the placement of key values within the tree. Very simply, a BST is defined by the following rule:

• All nodes in the left subtree have key values less than the key value of the parent
• All nodes in the right subtree have key values greater than the key value of the parent

The figure below shows an example of a binary search tree:

If you want to allow duplicate keys to a binary tree, you can do so as long as you be consistent in your implementation. That means you can either always add duplicate nodes to the left, or to the right. But not both in the same tree.