Binary Search Tree (BST)

BINARY SEARCH TREE

Binary Search Tree is a binary tree in which parent data is always greater than its left child data and always less than its right child data and again all sub tree are Binary tree.

Example of Left Binary Search Tree for 50 ,49 , 48 , 47, 45 , 44

Example of right Binary Search Tree for 50, 51, 52 , 53 , 54 , 55 , 56

Example of Binary Search Tree for 50 ., 15 , 80 , 7 , 17 , 70 , 16 , 56 , 79 , 75 

Explanation : First we insert 50 and than 15 now the question is where we insert 15. Since see 15 is less then 50 so it will come at left of 50.Now next we insert 80.since 80 is greater then 50 so it will come at right side of 50.same way we analyse the number and place it in appropriate place.

TRAVERSING SCHEMES IN BINARY SEARCH TREE:

There are three schemes for traversing binary search tree are:

1. Inorder

2. Preorder

3. Postorder

PROCEDURE FOR BINARY SEARCH TREE

struct node

{

    int data;

    struct node *lc , *rc ;

};

/* Main function */

main()

{

    struct node *root = NULL;

    int i , n , d ;

    void insert ( struct node **x , int d);

    /* Call with recursion */

    void inorder_R (struct node *root);

    void preorder_R (struct node *root);

    void postorder_R (struct node *root);

    /* Call with non recursion */

    void inorder (struct node *root);

    void preorder (struct node *root);

    void postorder (struct node *root);

    

    printf (" Enter number of node ");

    scanf (" %d ", &n );

    /* Create tree */

    for ( i=0 ; i<n ; i++)

    {

        printf ( " Enter data ");    

        scanf ( "%d", &d);

        insert (&root , d );

    }

    /* Traverse the tree */

    Inorder_R (root);

    Preorder_R(root);

    Postorder_R(root);

            OR

    Inorder(root);

    Preorder(root);

    Postorde(root);

}

/* Function for inserting node */

void insert ( struct node **x , int d )

{

    if ( ( *x) == NuLL)    

    {

        (*x) = (stuct node *) malloc (sizeof ((struct node ));

    {

        (*x)➞lc = NULL;

        (*x)➞rc = NULL;

        (*x)➞data = NULL;

    }

    }

    else

    {

        if (*x)➞data > d)

        {

            insert( & (*x)➞lc ), d);

        }

        else

        {

            insert( & (*x)➞rc ), d);

        }

    }

}

        

Points must be noted: 

d = is a pointer to structure which contain the address of deleted node.

ds = is a pointer to structure which contain the address of successor node.

dp = is pointer to structure which contain the address of predecessor node. 

/* Function for deleting node */

void delete_bst ( struct node **root , int x )

{

    struct node *d , *dp , *ds;

    int flag = 0;

    void search_bst(struct node **root , struct node **d , struct node **dp , int *flag , int x);

    search_bst ( root , &d , &dp , &flag , x );

    if (flag == 0)

    {

        printf (" Data not found " );

    }

    else

    {

        case 4;

        case 3;

        case 2;

        case 1;

    }

}

case 4: /* Delete node having both left & right child */

If ( d ➞ lc != NULL  && d ➞ rc != NULL)

{

    ds = d ➞ rc;

    dp = d;

    while ( ds ➞ lc != NULL)

    {

        dp = ds;

        ds = ds ➞ lc;

    }

    d ➞ data = ds ➞ data;

    d = ds;

}

case 3: /* Intermediate node having right child */

If ( d ➞ lc != NULL  && d ➞ rc != NULL)

{

      if ( dp ➞ lc == d)

    {

        dp ➞ lc = d ➞ rc;

    }

    else

    {

        dp ➞  rc = d ➞  rc;

    }

    free(d);

} 

        

case 2: /* Intermediate node having left child */

If ( d ➞ lc != NULL  && d ➞ rc != NULL)

{

      if ( dp ➞ lc == d)

    {

        dp ➞ lc = d ➞ lc;

    }

    else

    {

        dp ➞  rc = d ➞  lc;

    }

    free(d);

} 

case 1: /* Leaf node */

If ( d ➞ lc != NULL  && d ➞ rc != NULL)

{

      if ( dp ➞ lc == d)

    {

        dp ➞ lc = NULL;

    }

    else

    {

        dp ➞  rc = NULL;

    }

    free(d);

} 

/* Function for searching any node */

void search_bst( structnode **root, structnode **d, structnode **dp, int                                     *flag, int x)

{

    structnode *temp=(*root);

    while (temp !=NULL);

    {

        if (temp → data ==x)

            {

                (*d) = temp;

                (*flag) = 1;

                return ;

            }

        else

            {

                if (temp → data > x)

                    {

                        (*dp) = temp;

                        temp = temp → lc;

                    }

                else

                    {

                        (*dp) = temp;

                        temp =  temp → rc;

                    }

             }

    }                

}