Binary search Tree

    Binary search trees is a very useful data structure which takes linear time for search and retrieve unlike other data structure. We have seen heaps recently which takes O(log n) since it doesn’t maintain the sorted array in its structure. But BST maintains the sorted order.

   We have seen traversals already and on a BST when an in order traversal is done, it should return a sorted list. This is the main property of an BST.  So, heaps has an application of priority management and sorting. While BST has the main application in search.

Concept:

The below is an example of BST

                      15

              6               19

         3               17        20

    2        4

Do an in order traversal for the above tree gives, 2,3,4,6,15,17,19,20

This means, in-order traversal is the main core operation done in a BST to insert, delete items. Like in heap, we use up-bubble and down-bubble. We use in-order successor/predecessor concepts instead. To understand BST, in-order traversal must be understood really well.

Again note that, in-order traversal is: left-root-right.

Which means, visit the left-most and then root and then right.. We should never visit a right without visiting all left and all roots. If this point is very clear, in-order will be clear

If you see, after visiting 6(left),15(root), we still have 17(left) unvisited without which we should never visit 19(right). After 17(left) is visited, we get 19(root) and then 20 (right).

This is why in the above tree, if you insert 16, it will go below 17’s left by doing an in-order traversal.

The various operations in a BST are: search, insert, delete, min, max, successor, predecessor.

Before getting more into BST. we will discuss more about basic operations assuming BST is present already.

BST has one data item + 3 pointers. Parent, Left, Right.

Minimum value in a BST is nothing but the left most node

Maximum value in a BST is nothing but the right most node

All the above functions runs in O(n) time.