What is Binary Search Tree ?5 min read

1
167
What is Binary Search Tree

What is Binary Search Tree ?

A binary search tree (BST) is a binary tree, which is either empty or in which each node contains a key that satisfies the following conditions:

  1. All keys are distinct.
  2. For every node, X, in the tree, the values of all the keys in the left subtree are smaller than the key value of X.
  3. For every node, X, in the tree, the values of all the keys in the right subtree are greater than the key value of X.

Operations on BST

Insertion

Consider 20 is the new value to be inserted in the BST. The following figure shows the insertion of 20.

Insert 20 in BST

Here, starting with the root node, compare 20 with root (10). We find that 20 is greater than 10, hence traverse through the right subtree. Again compare 15 and 20. As 20 is greater than 15, traverse through the right subtree of 15. Compare 22 and 20. Now, as we can see that 20 is less than 22 and 22 doesn’t have any child node, insert 20 as the left child of 22.

Pseudo code

Let T be the BST, data as the value of the node, left and right as left and right children nodes, and X the node to be inserted.

Insert(T, X)
{
    if(T == NULL){
        T = new node;
        T->data = X;
        T->left = NULL;
        T->right = NULL;
    }
    else if(X > T->data){                //insert to right subtree
        T->right = Insert(T->right, X);
    }
    else if(X < T->data){                //insert to left subtree
        T->left = Insert(T->left, X);
    }
}

Average case space complexity = O(log N)

Worst case space complexity = O(N)

Searching

Suppose, we have to search item = 13.

Item to be searched = 13

First, we will compare 13 with root node 10. As it is greater than 10, we will traverse to the right subtree of 10. Then, we compare with 13 with 15. 13<15, so we go to the left subtree of 15. Thus we got 13 as the left child of 15.

Pseudo code

Let T be the BST, data as the value of the node, left and right as left and right children nodes and X the node to be searched.

Search(T, X){
    if(T == NULL)
        print(" Tree is NULL ");
    if(T->data == X)
        print(" Found X ");
    if(X > T->data)
        return Search(T->right, X);
    else
        return Search(T->left, X);
}

Deletion

The deletion algorithm first finds the location of the node X which contains the item to be deleted and also the location of the parent node P(X). The way X is deleted from the tree depends on the number of children of node X.

There are three cases:

  1. X has no children. Then X is deleted from T by simply replacing the location of X in the parent node P(X) by NULL.
  2. X has exactly one child. Then X is deleted from T by simple replacing the location of X in P(X) by the location of the only child of X.
  3. X has two children. Then X is deleted from T by replacing the location of X in P(X) by the smallest value of right subtree or by the largest value of the left subtree.
Case 1: No children present, 6 is deleted
Case 2: Only one child present, 22 is deleted
Case 3: Both the children are present, 15 is deleted

Pseudo Code

Let T be the BST, data as the value of the node, left and right as left and right children nodes and X the node to be deleted.

Delete(T, X){
    if(T == NULL)
        print(" Tree is NULL ");
    if(X < T->data){                   //delete in left subtree
        T->left = Delete(T->left, X);
        return T;
    }
    if(X > T->data){                  //delete in right subtree
        T->right = Delete(T->right, X);
        return T;
    }
    // element is found
    
    if(T->left==NULL and T->right==NULL){    //case 1
        temp = T;
        free(temp);
        return(NULL);
    }
    else if(T->left==NULL){                            //case 2
        temp = T;
        T = T->right;
        delete temp;
        return T;
    }
    else if(T->right==NULL){                         //case 2
        temp = T;
        T = T->left;
        delete temp;
        return T;
    }
    else{                                                      //case 3
        temp = T->right;
        while(temp->left != NULL)
            temp = temp->left;
        T->data = temp->data;
        T->right = Delete(T->right, temp->data);
        return T;
}

Source Code

Complexity for all three operations

Time complexity

Average case = O(log N)

Worst case = O(N)

Space Complexity

Average case = O(log N)

Worst case = O(N)

Suggested Post – Data Structures and Algorithms Study Guide

telegram channel link

– END –

What is Binary Search Tree ? What is Binary Search Tree in Data Structure ? Binary Search Tree in Data Structure, What is Binary Search Tree with full explanation ? What is Binary Search Tree with Examples ? What is Binary Search Tree Insertion ? What is Binary Search Tree Deletion ?

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here