Introduction to Binary Search tree

Introduction

A Binary Search tree is a fundamental data structure. It is used to implement other abstract data structures like sets, multisets, etc. It is more efficient than a standard binary tree. Operations like searching, insertion and deletion are performed faster and more efficiently in a binary search tree.

What is the difference between a binary tree and a binary search tree?

Binary trees and binary search trees are non-linear data structures. Each node in the binary tree and binary search tree can have at most two children. Binary search trees are node-based. The elements are added and deleted based on the values present in each node compared with the parent node.

A binary search tree has a left subtree and a right subtree. Binary trees do not follow any order while insertion and deletion, which in binary search tree elements are inserted and deleted in a specific manner. This is why operations like insertion, deletion, and searching are expected much faster in binary search trees than in binary trees.

To know more check this out.

What is the basic idea behind binary search trees?

In a binary search tree, every element present in the left subtree of each node must have a value lesser than the value of its parent. Every element present in the right subtree of each node must have a value greater than the value of its parent.

Example1: To store elements from 1 to 10 such that 7 is the root. All values less than 7 will be held in the nodes of the left subtree. All the values greater than 7 will be stored in the nodes of the right subtree.

Example2: Diagram demonstrating how elements are arranged in a binary search tree.

The above example is that of a binary search tree. In this tree, the root is 15. The element in the next level is 11 and 26. Since 11 is smaller than 15, the element is inserted into the node present on the left. Since 26 is greater than 15, it is inserted in the node present in the right to 15.

The element to be added next is 8. The number is first compared to the root that has the value 15. Since 8 is less than 15, 8 is moved to the left subtree of 15. In the left subtree, the root value is 11. 11 when compared with the value to be entered that is 8,8 is less than 11, so it is moved to its left subtree. Since no elements are present in the left subtree, a new node is created to the left of 11, and the node with the value 8 is inserted.

The element to be added next is 30. The number is first compared to the root that has the value 15. Since 30 is greater than 15, 30 is moved to the right subtree of 15. In the right subtree, the root value is 26. 26 when compared with the value to be entered, 30,30 is greater than 26, so it is moved to its right subtree. Since no elements are present in the right subtree, a new node is created to the right of 26, and the node with the value 30 is inserted.

The rest of the elements are added to it similarly.

Basic operations in a binary search tree

There are mainly 3 operations in a binary search tree: searching, insertion, and deletion.

Searching

A binary search can be performed if we have a sorted array. To search for a number, we first find the midpoint of the element present in the middle of the array. We compare the number to be searched with the number currently in the midpoint. The search operation is complete if the number searched is the same as the number in the middle. Or else, If the number searched is less than the midpoint, we check on to the left side of the array, that is after the first step in binary search where the area to be searched covers the entire array, we reduce the area to be searched to the midpoint.

If the number to be searched is greater than the number in the midpoint, then the search area will be reduced from the center of the array to the end of the array.

This process continues until the element to be searched is the midpoint of the area to be checked.

If the total number to be searched in the first step is n, then in the second step, the total number to be compared will be reduced to half of n, the tree’s root,n/2. The searching operation in the binary search tree is similar to these.

In the first step, the root element is considered as the key. The element to be searched is compared to the critical value. If the key is greater than the value to be searched, the key is made as to the left node of the current key. The left subtree is searched. If the key is less than the value to be searched, the key is made as to the right node of the current key. The right subtree is searched.

This process continues until the key value is null. Even in the tree’s leaf nodes, the element was not found or when the element was found.

Now let’s look at the code illustrating searching of an element in a binary search tree in C programming language:

void search(BST *root, int data)

{

   BST *save,*ptr;

   if (root == NULL)//failed condition where the required node is not found

   {

       loc= NULL;// assigning values as null due to failed search

       par=NULLthe ;

   }

   if (data == root -> info)// search successful

   {

   loc = root;// assigning values

   par = NULL;

   return;

   }

   if (data < root->info) // data less than present node, hence traversing towards left subtree

   {

       save = root;

       ptr = root->left;

   }

   else

   {

       save = root;// data greater than present node, hence traversing towards right subtree

       ptr = root -> right;

   }

   while( ptr != NULL)

   {

       if (ptr -> info == data)

       {

           loc= ptr;

           par = save;

           return;

       }

       if(data< ptr->info)//traversal

       {

           save = ptr;

           ptr = ptr->left;

       }

       else

       {

           save = ptr;

           ptr = ptr->right;

       }

   }

   loc = NULL;

   par = save;

   return;

}

Insertion

The search operation is also a traversal operation. This search operation is done to execute insertion operations. When an element is given to perform insertion, the element is first compared with the trees’ root value. Based on this, if the value to be added is less than that of the root, the element is moved to the left subtree and is compared with the element present, and the step is continued until it reaches a leaf node and a new node is added where the element is assigned. If the value to be added is greater than that of the root, the element is moved to the right subtree and is compared with the element present and the step is continued until it reaches a leaf node and a new node is added where the element is assigned.

Code illustrating the insertion of an element in a binary search tree in C programming language:

struct node*insert(struct node*R, int data)

{

if (R == NULL)

{

           R = (struct node*)malloc(sizeof(struct node));//allocating new node

           R->info = data;//assigning the data to new node

           R->left = R->right = NULL;//assigning the child node as NULL

           return R;

}

else if (data < R->info)

           R->left = insert(R->left, data);

else if (data > R->info)

           R->right = insert(R->right, data);

           return R;

}

Deletion

There are 3 cases when deleting an element from a tree.

Case 1:

The element to be deleted is in the leaf node. In this case, the element can be deleted easily by removing the leaf node. The conditions of the binary search tree will not be violated in this case.

Case 2:

The element to be deleted is present in a node that has a single child. In this case, first, we perform a search operation in the binary search tree and find the parent of the node to be deleted. The link of the parent node must be changed from the node to be deleted to its child node. When deleted like this, the conditions of a binary search tree will not be violated.

Case 3:

The element to be deleted is present in a node having both left and right children. In this, there are chances that the conditions of the binary tree may be violated. First, do a search operation and find the node to be deleted. Next, find the inorder successor of the node. Write the contents of the inorder successor. Now delete the inorder successor. To perform this, we can also use inorder predecessor. This method of finding the inorder successor is needed to be done only in cases where the right child of the node has a value or is not empty. In such cases, the inorder successor can be found by spotting the lowest value in the right child of the node to be deleted.

Code illustrating deletion of an element in a binary search tree in C programming language:

// A function to do inorder traversal of BST

void inorder(struct node* root)

{

    if (root != NULL) {

        inorder(root->left);

        printf("%d ", root->info);

        inorder(root->right);

    }

}



/* If a non-empty binary search

   Tree is given, return the node

   with the minimum key value found in

   that tree*/



struct node* minValueNode(struct node* node)

{

    struct node* current = node;

    while (current && current->left != NULL)

        current = current->left;

 

    return current;

}

/* if a binary search tree

   and a key is given, this function

   deletes the key and

   returns the new root */



struct node* DeleteNode(struct node* root, int data)

{

    if (root == NULL)

        return root;

    if (data < root->info)

        root->left = DeleteNode(root->left, data);

    else if (data> root->info)

        root->right = DeleteNode(root->right, data);

    else {

        if (root->left == NULL) {

            struct node* temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL) {

            struct node* temp = root->left;

            free(root);

            return temp;

        }

        struct node* temp = minValueNode(root->right);

        root->info = temp->info;

 

        root->right = DeleteNode(root->right, temp->info);

    }

    return root;

}

The time complexity of a binary search tree is O(log n).

The space complexity is O ( n ).

Check out this problem - Mirror A Binary Tree

Types of Binary Search tree

There are variations in the Binary Search tree to optimize and increase the efficiency of the binary search tree. They are the AVL tree and the Red-Black tree. These two variations improve the efficiency of operations like searching, insertion, and deletion.

Applications of a binary search tree

Binary search trees help in the easy sorting of data.
It provides an efficient way for storing sorted data.
It also provides a better means for indexing and multi-level indexing.

Frequently Asked Questions

What are binary trees?

Binary trees are tree data structures where each node has at most two child nodes. These child nodes can be called the left child and the right child.

What is a binary search tree?

Binary search trees are data structures that efficiently represent and perform certain tree operations, such as insertion, deletion, and searching. In a binary search tree, each node has values less than it to its left subtree and values greater than it on the right subtree.

What are the advantages of using binary search trees?

Binary search trees provide a better and efficient means for data handling. It provides a better means for insertion, deletion and other operations.

What is the time and space complexity of searching in a binary search tree?

The time complexity of performing a search in a binary search tree is O(log n). The space complexity is O ( n ).

What are the uses of binary search trees?

A binary search tree is helpful for multilevel indexing, various search algorithms, maintaining sorted data, etc.

Conclusion

A binary search tree is a fundamental data structure. It gives us a better way to handle tree data structure. It provides an efficient, more accessible, and faster method to perform operations on a tree-like traversal, searching, insertion and deletion.

You can practice interview questions based on binary search trees at code studio. You can also check out the Basics of C++ with Data Structures and Algorithms course offered by Coding Ninjas to share your knowledge.

Introduction to Binary Search Tree