Binary Search Tree Data Structure
Free Data Structures and Algorithms courses with real-time projects Start Now!!
As we discussed in the previous article, the binary search tree is one of the types of trees with some specific properties. A binary search tree is quick, efficient, and easy to implement. In this article, we will learn the working of a binary search tree, its properties, and its implementation.
Binary search tree
BST, short for Binary search tree is a binary tree with specific following properties.
1. The nodes in the left subtree must be less than the root node
2. The nodes in the right subtree must be greater than the root node.
3. The left and the right subtrees must also be binary trees.
The above properties apply to each node of the binary tree for it to be a BST.
Operations on Binary Search Tree in data Structure
1. Searching in BST
Finding the location of an element in the BST
Algorithm
search(root) If root == NULL return NULL; If Value == root->data return root->data; If Value < root->data return search(root->left) If Value > root->data return search(root->right)
2. Inserting element in BST
Inserting a new element in the BST
Algorithm
createNode(newvalue) If node == NULL return createNode(newvalue) if (newvalue < node->data) node->left = insert(node->left, newvalue); else if (newvalue > node->data) node->right = insert(node->right, newvalue); return node;
3. Deleting element from BST
deleting an existing element from BST
Case 1: if a node is to be deleted from the Leaf node.
- Simply Delete the node from the leaf node.
Case 2: if the node that has to be deleted has 1 child
- Replace node with the child node
- Remove child node from the original position
Case 3: if the node that has to be deleted has 2 child
- Retrieve inorder successor of the node.
- Replace node with the inorder successor
- Remove inorder successor from its original position.
Working of Binary Search Tree
Let us take an example to demonstrate the working of BST with insert and delete operations
Step 1: insert 50
Step 2: insert 75
Step 3: insert 90
Step 4: insert 25
Step 5: insert 40
Step 6: insert 62
Step 7: insert 70
Step 8: delete 90. This is case 1 deletion.
Step 9: insert 92
Step 10: delete 25. This is case 2 deletion.
Step 11: delete 75. This is case 3 deletion.
Step 12: insert 30
Implementation of Binary Search Tree in C
#include <stdio.h> #include <stdlib.h> struct node { int key; struct node *left, *right; }; struct node *newNode(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inorderTraversal(struct node *root) { if (root != NULL) { inorderTraversal(root->left); printf("%d -> ", root->key); inorderTraversal(root->right); } } struct node *insertNew(struct node *node, int Value) { if (node == NULL) return newNode(Value); if (Value< node->key) node->left = insertNew(node->left, Value); else node->right = insertNew(node->right, Value); return node; } struct node *minValueNode(struct node *node) { struct node *current = node; while (current && current->left != NULL) current = current->left; return current; } struct node *deleteNode(struct node *root, int Value) { if (root == NULL) return root; if (Value < root->key) root->left = deleteNode(root->left, Value); else if (Value > root->key) root->right = deleteNode(root->right, Value); 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->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } int main() { struct node *root = NULL; root = insertNew(root, 8); root = insertNew(root, 3); root = insertNew(root, 1); root = insertNew(root, 6); root = insertNew(root, 7); root = insertNew(root, 10); root = insertNew(root, 14); root = insertNew(root, 4); printf("Inorder traversal: "); inorderTraversal(root); printf("\nAfter deleting 10\n"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorderTraversal(root); }
Binary Search Tree Implementation in C++
#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; struct node { int key; struct node *left, *right; }; struct node *newNode(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } void inorderTraversal(struct node *root) { if (root != NULL) { inorderTraversal(root->left); printf("%d -> ", root->key); inorderTraversal(root->right); } } struct node *insertNew(struct node *node, int Value) { if (node == NULL) return newNode(Value); if (Value< node->key) node->left = insertNew(node->left, Value); else node->right = insertNew(node->right, Value); return node; } struct node *minValueNode(struct node *node) { struct node *current = node; while (current && current->left != NULL) current = current->left; return current; } struct node *deleteNode(struct node *root, int Value) { if (root == NULL) return root; if (Value < root->key) root->left = deleteNode(root->left, Value); else if (Value > root->key) root->right = deleteNode(root->right, Value); 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->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } int main() { struct node *root = NULL; root = insertNew(root, 8); root = insertNew(root, 3); root = insertNew(root, 1); root = insertNew(root, 6); root = insertNew(root, 7); root = insertNew(root, 10); root = insertNew(root, 14); root = insertNew(root, 4); cout << "Inorder traversal: "; inorderTraversal(root); cout << "\nAfter deleting 10\n"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorderTraversal(root); }
BST Implementation in JAVA
public class BinarySearchTree { class Node { int key; Node left, right; public Node(int item) { key = item; left = right = null; } } Node root; BinarySearchTree() { root = null; } void insert(int key) { root = insertKey(root, key); } Node insertKey(Node root, int key) { if (root == null) { root = new Node(key); return root; } if (key < root.key) root.left = insertKey(root.left, key); else if (key > root.key) root.right = insertKey(root.right, key); return root; } void inorder() { inorderRec(root); } void inorderRec(Node root) { if (root != null) { inorderRec(root.left); System.out.print(root.key + " -> "); inorderRec(root.right); } } void deleteKey(int key) { root = deleteRec(root, key); } Node deleteRec(Node root, int key) { if (root == null) return root; if (key < root.key) root.left = deleteRec(root.left, key); else if (key > root.key) root.right = deleteRec(root.right, key); else { if (root.left == null) return root.right; else if (root.right == null) return root.left; root.key = minValue(root.right); root.right = deleteRec(root.right, root.key); } return root; } int minValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } return minv; } public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); tree.insert(8); tree.insert(3); tree.insert(1); tree.insert(6); tree.insert(7); tree.insert(10); tree.insert(14); tree.insert(4); System.out.print("Inorder traversal: "); tree.inorder(); System.out.println("\n\nAfter deleting 10"); tree.deleteKey(10); System.out.print("Inorder traversal: "); tree.inorder(); } }
Binary Search Tree Implementation in Python
class Node: def __init__(self, key): self.key = key self.left = None self.right = None def inorderTraversal(root): if root is not None: inorderTraversal(root.left) print(str(root.key) + "->", end=' ') inorderTraversal(root.right) def insertnew(node, value): if node is None: return Node(value) if value< node.key: node.left = insertnew(node.left, value) else: node.right = insertnew(node.right, value) return node def minValueNode(node): current = node while(current.left is not None): current = current.left return current def deleteNode(root, value): if root is None: return root if value < root.key: root.left = deleteNode(root.left, value) elif(value> root.key): root.right = deleteNode(root.right, value) else: if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp temp = minValueNode(root.right) root.key = temp.key root.right = deleteNode(root.right, temp.key) return root root = None root = insertnew(root, 8) root = insertnew(root, 3) root = insertnew(root, 1) root = insertnew(root, 6) root = insertnew(root, 7) root = insertnew(root, 10) root = insertnew(root, 14) root = insertnew(root, 4) print("Inorder traversal: ", end=' ') inorderTraversal(root) print("\nDelete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorderTraversal(root)
Advantages of Binary Search Tree
1. Searching is very easy in BST. At each step, we get to know which subtree might contain the element.
2. Insertion and deletion in BST is faster than arrays or linked lists
3. BST is very efficient in terms of complexity.
Complexity of Binary Search Tree
Space complexity for all operations in BST in O(n)
Operation | Best case | Average case | Worst Case |
Searching | O(log n) | O(log n) | O(n) |
Insertion | O(log n) | O(log n) | O(n) |
deletion | O(log n) | O(log n) | O(n) |
Applications of BST
1. It is implemented for dynamic sorting
2. It manages virtual memory area in UNIX kernel
3. It’s useful for multilevel indexing in database
Conclusion
BST is a fast and efficient algorithm with many real-world applications and advantages. We learned working and implementation of BST in different programming languages. In future articles, we will learn about AVL trees and, B-Tree, etc.
We work very hard to provide you quality material
Could you take 15 seconds and share your happy experience on Google