We already had a brief look at trees in Lesson 7, The Java Collections Framework and Generics let's look at a special implementation of trees known as binary search trees (BSTs).
To understand BSTs, let's take a look at what binary tree is. A tree in which each node in the tree has at most two child nodes, is a binary tree.
A BST is a special implementation of a binary tree, where the left-child node is always less than or equal to the parent node, and the right-child node is always greater than or equal to the parent node. This unique structure of the binary search tree makes it easier to add, delete, and search for elements of the tree. The following diagram represents a BST:
Figure 8.2: Representation of a binary search tree
The applications of binary search tree are as follows:
To implement a dictionary.
To implement multilevel indexing in a database.
To implement a searching algorithm.