EDUCBA

EDUCBA

MENUMENU
  • Explore
    • Lifetime Membership
    • All in One Bundles
    • Fresh Entries
    • Finance
    • Data Science
    • Programming and Dev
    • Excel
    • Marketing
    • HR
    • PDP
    • VFX and Design
    • Project Management
    • Exam Prep
    • All Courses
  • Blog
  • Enterprise
  • Free Courses
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Binary Search Tree in Data Structure

Binary Search Tree in Data Structure

Updated March 13, 2023

Binary search tree in data structure

What is Binary Search Tree in Data Structure

The binary search tree is the data structure used to maintain a sorted orderly list of elements. In this tree, each node can have a maximum of only two children. The format followed while storing the values is that the left node of the main node should have a smaller value than the main node, while the right one should have a greater value than the main node value. This pattern is followed for all the sub-nodes on the left and right sides of the main node. Subtrees of each of the individual nodes of the tree also possess both of the properties mentioned above, and hence they also act as BST, i.e., Binary Search Tree.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

A particular value or number stored inside the binary tree node can be easily searched in the O (log (n)) complexity of time. This article will study the working and implementation and application of binary search trees using the C programming language.

Example of the Binary Search Tree

The main node should always possess a value that is greater than the left node or all of the descendants of the left node and should be smaller than the right node and all its children. The same rule applies to all of the other nodes. The following tree is the correct binary search tree example –

Cap1

The following tree is not the proper example of the binary search tree because the node containing the value 13 should possess a value greater than 26, which is its parent or main node. Hence, the single node that follows the rules makes the below tree, not a binary search tree. Each of the nodes of the tree must follow the rules.

Cap2

Implementation of the Binary Search Tree

Now, let us see how we can make use of the binary search tree data structure concept by implementing it using a C programming language. The following is the C program which contains all the proper comments explaining all the operations that are carried out, and the names of the functions are self-explanatory –

// C program for implementing the Binary search tree data structure
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *leftNode, *rightNode;
};
// Creation of the new node in the tree
struct node *newlyCreatedNode(int element) {
struct node *temporaryNode = (struct node *)malloc(sizeof(struct node));
temporaryNode->key = element;
temporaryNode->leftNode = temporaryNode->rightNode = NULL;
return temporaryNode;
}
// Traversing all the nodes in order
void traversalInOrder(struct node *mainRootNode) {
if (mainRootNode != NULL) {
// Left node traversal
traversalInOrder(mainRootNode->leftNode);
// Main Root node traversal
printf("%d -> ", mainRootNode->key);
// Right node traversal
traversalInOrder(mainRootNode->rightNode);
}
}
// Insert a new item in the binary search tree
struct node *addElement(struct node *node, int key) {
// In case if the tree seems to be empty then return a newly created node
if (node == NULL) return newlyCreatedNode(key);
// Insert a new element that is node after traversing the right side
if (key < node->key)
node->leftNode = addElement(node->leftNode, key);
else
node->rightNode = addElement(node->rightNode, key);
return node;
}
// Search for the succesor that is found by traversing inorder format
struct node *minimumValueNode(struct node *node) {
struct node *presentNode = node;
// Search the node which is present at the most left side of the tree that is left most leaf
while (presentNode && presentNode->leftNode != NULL)
presentNode = presentNode->leftNode;
return presentNode;
}
// Remove the node from the tree
struct node *removeOrDeque(struct node *mainRootNode, int key) {
// In case if the tree is completely empty then return the same main root node that is supplied
if (mainRootNode == NULL) return mainRootNode;
// Search for the node which is to be deleted
if (key < mainRootNode->key)
mainRootNode->leftNode = removeOrDeque(mainRootNode->leftNode, key);
else if (key > mainRootNode->key)
mainRootNode->rightNode = removeOrDeque(mainRootNode->rightNode, key);
else {
// In case if the current node has only one of the offspring or none of the child
if (mainRootNode->leftNode == NULL) {
struct node *temporaryNode = mainRootNode->rightNode;
free(mainRootNode);
return temporaryNode;
} else if (mainRootNode->rightNode == NULL) {
struct node *temporaryNode = mainRootNode->leftNode;
free(mainRootNode);
return temporaryNode;
}
// In case if the current node has two child nodes
struct node *temporaryNode = minimumValueNode(mainRootNode->rightNode);
// Replace the the node which is being removed or deleted in the place of successor in order
mainRootNode->key = temporaryNode->key;
// Remove the identified successor node detected in order traversal
mainRootNode->rightNode = removeOrDeque(mainRootNode->rightNode, temporaryNode->key);
}
return mainRootNode;
}
// Controller for carrying out all the operations and manipulating all the data
int main() {
struct node *mainRootNode = NULL;
mainRootNode = addElement(mainRootNode, 8);
mainRootNode = addElement(mainRootNode, 3);
mainRootNode = addElement(mainRootNode, 1);
mainRootNode = addElement(mainRootNode, 6);
mainRootNode = addElement(mainRootNode, 7);
mainRootNode = addElement(mainRootNode, 10);
mainRootNode = addElement(mainRootNode, 14);
mainRootNode = addElement(mainRootNode, 4);
printf("Traversing the tree in order: ");
traversalInOrder(mainRootNode);
printf("\n The contents of the binary tree after removing the node with value 10 \n");
mainRootNode = removeOrDeque(mainRootNode, 10);
printf("Traversing the tree in order : ");
traversalInOrder(mainRootNode);
}

The output of the above code after execution is as shown below –

Binary search tree in data structure output

Complexity

Let us discuss the time and space complexities of using the binary search tree. The space complexity of the binary search tree is O(n) while carrying out each of the operations like search, insert or delete for manipulating the nodes and contents. The time complexity in each of the cases for each of the operations is as shown in the below table –

Operations performed Search Insertion deletion
Complexity in Best Case Scenario O (log n) O (log n) O (log n)
Complexity in worst Case Scenario O (n) O (n) O (n)
Complexity in average Case Scenario O (log n) O (log n) O (log n)

Applications of a Binary Search Tree

A binary search tree is used in many algorithms and computer applications. Some of them are listed below –

  • Dynamic Sorting internally makes use of a binary search tree.
  • In the database, multilevel indexing is implemented by using a binary search tree.
  • In the UNIX kernel, the virtual memory areas are managed by using a binary search tree.

Conclusion

A binary search tree is the data structure in which each node should have a maximum of two child nodes, and the values of all the nodes on the left should have a value that is less than the current node, while on the right should have a value greater than the current one.

Recommended Articles

This is a guide to a Binary search tree in the data structure. Here we discuss the working and implementation and application of binary search tree using the C programming language. You may also look at the following articles to learn more –

  1. Oracle B Tree Index
  2. B Tree in Data Structure
  3. What is a Decision Tree?
  4. Types of Trees in Data Structure
ADVERTISEMENT
All in One Excel VBA Bundle
500+ Hours of HD Videos
15 Learning Paths
120+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
Financial Analyst Masters Training Program
2000+ Hours of HD Videos
43 Learning Paths
550+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Data Science Bundle
2000+ Hour of HD Videos
80 Learning Paths
400+ Courses
Verifiable Certificate of Completion
Lifetime Access
ADVERTISEMENT
All in One Software Development Bundle
5000+ Hours of HD Videos
149 Learning Paths
1050+ Courses
Verifiable Certificate of Completion
Lifetime Access
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

By continuing above step, you agree to our Terms of Use and Privacy Policy.
*Please provide your correct email id. Login details for this Free course will be emailed to you

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more

🚀 Extended Cyber Monday Price Drop! All in One Universal Bundle (3700+ Courses) @ 🎁 90% OFF - Ends in ENROLL NOW