Introduction
Binary search trees are perhaps one widely known and used data structures. They are easy to build, robust and are very efficient, so much so that almost all on an average happen in Θ(lg n) time. The binary tree is at its worst when all the element in it are in a straight line, in such a case operations take about O(n). One way to avoid a binary tree from loosing balance is to build an AVL Tree.
Structure of a binary tree
Every node of a binary tree consists of a key, a left, a right and a p pointer where the left and right pointers point to the children and the p pointer points to the parent. If either a left or a right pointer does not exists those pointers are set to null. Only the root node has its p pointer set to NULL in a binary tree.
The most important feature of a binary search tree is known as, well, the binary search tree property. If x is a node then the node to the left of x will be less than or equal to its key and the node to the right will be greater than or equal to its key. The figure below, shows an example of a tree satisfying the BST property.
An interesting property of this arragement is that if we traverse this tree in order, the nodes of the tree would be visted in ascending order. This cannot be used to sort because it turns out to be inefficient compared to sorting algorithms, that have a run time of O(n lg n). This is because inserting a node into a binary tree takes O(lg n) and to insert n nodes we need O(n lg n) + Θ(n) to traverse all the nodes.
Thinking a little more about the BST property we see that if we continue to follow the left child all the way we will eventually get to the smallest element in the tree. Conversely if we follow the right child all the way we will get to the greatest element in the tree.