The Binary Search Tree Data Structure

The binary search tree data structure is inspired by binary search algorithm. The tree inherits the same advantages as that algorithm.

The data is inserted in a sorted manner. It has inserting and deleting benefits of the linked list. This is the most popular data structure in Computer Science with many applications.

The binary search tree as any trees consists of nodes. Each node has no, one ore two children, but no more than two. This is why it is called binary. The top node is called the root. Everything that is on the right side of the root must be greater that the root, and every node one the left side should be smaller than the root. The child that has the same value must go to the left.

To get the most efficiency from the binary search tree, the tree should
be balanced, meaning that for all the nodes in the tree, the difference
between the hights of the left and right sub-trees must not be greater
than one.