C++ Data Structures and Algorithms

Building a binary search tree ADT

A binary search tree (BST) is a sorted binary tree, where we can easily search for any key using the binary search algorithm. To sort the BST, it has to have the following properties:

• The node's left subtree contains only a key that's smaller than the node's key
• The node's right subtree contains only a key that's greater than the node's key
• You cannot duplicate the node's key value

By having the preceding properties, we can easily search for a key value as well as find the maximum or minimum key value. Suppose we have the following BST:

As we can see in the preceding tree diagram, it has been sorted since ...