Binary search tree–Introduction

“We have seen binary search already in old articles where we divide a sorted array from median and branch accordingly to find the element in half the time. Binary search tree’s are representation which depict on array from the median”

See Also

http://analgorithmaday.blogspot.com/2011/02/tree-traversal-for-binary-trees.html

http://analgorithmaday.blogspot.com/2011/01/tree-data-structureexplained.html

Introduction

     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.

Code

class BST {

public:

    int data;

    BST* parent;

    BST* left;

    BST* right;

};

// inorder traversal of BST

// MUST GIVE SORTED OUTPUT

void printBST(BST* root)

{

    if(root == NULL) return;

    printBST(root->left);

    cout<<root->data;

    printBST(root->right);

}

// left most is MIN

int min(BST* root)

{

    int minval=0;

    while(root != NULL) {

        minval = root->data;

        root = root->left;

    }

    return minval;

}

// right most is MAX

int max(BST* root)

{

    int maxval=0;

    while(root != NULL) {

        maxval = root->data;

        root = root->right;

    }

    return maxval;

}

Important points:

• As you can see printBST does a in-order traversal to print the BST to give a sorted input
• 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.