Binary Search Tree

As introduced recently in class a BST (Binary Search Tree) is a special type of a binary tree that has a new property. The special thing about a BST is that every element in a tree is larger than its left child and smaller than its right child (if they exist). The element of the tree (nodes) don't have to be numbers, they should simply by comparable objects. Arranging elements into a BST can be viewed as sorting the elements, since such arrangement makes it easier to search through all the elements. In particular, this turns the linear search with the order of n into a binary search which has a complexity of log₂(n).