A Binary Search Tree in data structures is a set of nodes organized in such a way that they all have the same BST characteristics. It assigns a pair of keys and values to each node. You usually employ a binary search tree for multiple indexing. Binary search trees are also good at implementing searching algorithms.
By completing this tutorial you will understand the technical fundamentals of binary search trees with all the necessary details and practical examples.
Properties of Binary Search Trees
- The node's left subtree contains only nodes with data values lower than the parent node's data.
- The node's right subtree contains only nodes with data higher than the parent node's data.
- In a BST, the left and right subtree must also be a binary search tree.
- Each node in the binary search tree can have at most two children.
These are the properties associated with BST in data structures. Next, you will explore various operations you can perform on BST in data structures.
Operations On Binary Search Trees
You can execute two operations on a binary search tree:
- Insertion operation
- Deletion operation
Let's discuss them in detail.
Insertion Operation on BST in Data Structures
You will start with the root node. You must begin by comparing nodes with the element to be inserted. If the element to be inserted is small compared to the node's element, you must move to the left subtree. Otherwise, you will move to the right subtree.
|
Code: // A c++ program to perform insertion in binary search tree. #include <bits/stdc++.h> using namespace std; // A class to create node class Binarysearchtree { int data; Binarysearchtree *left, *right; public: // Default constructor. Binarysearchtree(); // Parameterized constructor. Binarysearchtree(int); // Insert function. Binarysearchtree* Insert(Binarysearchtree*, int); // Inorder traversal. void Inorder(Binarysearchtree*); }; // Default Constructor definition. Binarysearchtree ::Binarysearchtree() : data(0) , left(NULL) , right(NULL) { } // Parameterized Constructor definition. Binarysearchtree ::Binarysearchtree(int data1) { data = data1; left = right = NULL; } // Insert function definition. Binarysearchtree* Binarysearchtree ::Insert(Binarysearchtree* root, int data1) { if (!root) { //we will insert the first node, if root is NULL. return new Binarysearchtree(data1); } // Insert data. if (data1> root->data) { // Insert right node data, if the 'data1' // to be inserted is larger than 'root' node data. // Process right nodes. root->right = Insert(root->right, data1); } else { // Insert left node data, if the 'data1' // to be inserted is larger than 'root' node data. // Process left nodes. root->left = Insert(root->left, data1); } // Return 'root' node, after insertion. return root; } // Inorder traversal function. // This gives data in sorted order. void Binarysearchtree ::Inorder(Binarysearchtree* root) { if (!root) { return; } Inorder(root->left); cout << root->data << “ ”; Inorder(root->right); } // Driver code int main() { Binarysearchtree bst, *root = NULL; root = bst.Insert(root, 5); bst.Insert(root, 3); bst.Insert(root, 2); bst.Insert(root, 4); bst.Insert(root, 7); bst.Insert(root, 6); bst.Insert(root, 8); cout<<"created Binary search tree: \n"; bst.Inorder(root); return 0; } |
Deletion Operation on the Binary Search Trees in Data Structures
When you attempt to delete a node, three scenarios might occur.
- Node to be deleted have no children: In this case, you can delete the node without any repercussions.
- Node to be deleted has precisely one child: In this case, you have to ensure that its child should be connected back to the deleted node's parent after deletion.
- Node to be deleted have two children: In this case, you have to search and replace the deleted node with its successor.
|
Code: // A C++ program to perform deletion on a BST #include <bits/stdc++.h> using namespace std; struct node { int data; struct node *left, *right; }; // A function to create a BST node struct node* newNode(int key) { struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->data = key; temp->left = temp->right = NULL; return temp; } // A function to display BST void display(struct node* root) { if (root != NULL) { display(root->left); cout << root->data<<" "; display(root->right); } } // A function to insert a node in the binary search tree struct node* insert(struct node* newnode, int data) { // If the tree is empty, we will return a new node if (newnode == NULL) return newNode(data); /* Otherwise, recur down the tree */ if (data < newnode->data) newnode->left = insert(newnode->left, data); else newnode->right = insert(newnode->right, data); return newnode; } // A function returns the node with the minimum data value found in that tree. struct node* minvalue(struct node* node) { struct node* temp = node; while (temp && temp->left != NULL) temp= temp->left; return temp; } // A function to perform deletion on BST struct node* deleteNode(struct node* root, int data) { // base case if (root == NULL) return root; // If the element to be deleted is smaller than the root's data, then it lies in left subtree if (data < root->data) root->left = deleteNode(root->left, data); // If the element to be deleted is greater than the root's data, then it lies in right subtree else if (data > root->data) root->right = deleteNode(root->right, data); // if data is same as root's data, then This is the node // to be deleted else { // node has no child if (root->left==NULL and root->right==NULL) return NULL; // node with either one child or no child else if (root->left == NULL) { struct node* t = root->right; free(root); return t; } else if (root->right == NULL) { struct node* t = root->left; free(root); return t; } // for a node with two children, we will get the inorder successor struct node* t = minvalue(root->right); root->data = t->data; // Delete the inorder successor root->right = deleteNode(root->right, t->data); } return root; } int main() { // lets create an empty binary search tree struct node* root = NULL; root = insert(root, 5); root = insert(root, 3); root = insert(root, 2); root = insert(root, 4); root = insert(root, 7); root = insert(root, 6); root = insert(root, 8); cout << "Original Binary search tree: \n"; display(root); cout << "\n\nDelete 2\n\n"; root = deleteNode(root, 2); cout << "modified binary search tree \n"; display(root); cout << "\n\nDelete 5\n\n"; root = deleteNode(root, 5); cout << "modified binary search tree \n"; display(root); return 0; } |
Applications of Binary Search Trees
- BST are used to accomplish indexing and multi-level indexing.
- They are also capable of implementing various search algorithms.
- It aids in organizing a data stream.
- Self-balancing BSTs are used to implement TreeMap and TreeSet data structures.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!
Next Steps
Your next stop in understanding data structures would be "AVL Trees in data structure". An AVL tree is a height-balanced BST in which the height of the left subtree and right subtree can differ at most by one.
Maybe you are looking for a more comprehensive learning of software development which can help you forge a strong career in software development. If that is indeed the case, explore Simplilearn's Post Graduate Program in Full Stack Web Development in collaboration with Caltech CTME, the behemoth university in technology education. This coding bootcamp program offers the learning, practice, and certifications that you need to not just get work-ready, but stand a chance to compete for top software development jobs anywhere in the world.
For now, if you have questions or need clarifications regarding this "binary trees in data structures" tutorial, do let us know by leaving them in the comments section you can find at the bottom of this page. Our expert team will review and ensure that they are answered at the earliest.
