In this tutorial, you learn how Binary Search Tree functions. Additionally, you will discover working instances of Binary Search Tree in C, C++, Java, and Python.
In this article, you will learn-
What is a Binary Search Tree?
The binary search tree is an advanced algorithm used for analyzing the node, its left and right branches, which are displayed in a tree structure and returning the worth. The BST is formulated on the architecture of an essential binary search algorithm; thus it enables quicker lookups, insertions, and removals of nodes. This makes the program really quick and exact.
A binary search tree is a data structure that rapidly allows us to keep an arranged list of numbers.
• It is known as a binary tree because each tree node has a maximum of two children.
• It is known as a search tree since it tends to be used to look for the presence of a number in O(log(n)) time.
The properties that different a binary search tree from a regular binary tree is
- All nodes of the left subtree are not exactly the root node
- All nodes of the right subtree are more than the root node
- Both subtrees of every node are likewise BSTs for example they have the above two properties
The binary tree on the right is certainly not a binary search tree because the right subtree of the node “3” contains a worth smaller than it.
There are two essential tasks that you can perform on a binary search tree:
Search Operation
The algorithm relies upon the property of BST that if each left subtree has values underneath root and each right subtree has values above the root.
In the event that the worth is beneath the root, we can say without a doubt that the value isn’t in the right subtree; we need to possibly look in the left subtree and if the value is above the root, we can say without a doubt that the value isn’t in the left subtree; we need to just search in the right subtree.
Algorithm:
If root == NULL return NULL; If number == root->data return root->data; If number < root->data return search(root->left) If number > root->data return search(root->right)
Let us try to visualize this with a diagram.
On the off chance that the value is discovered, we return the value so it gets spread in every recursion step as demonstrated in the picture underneath.
In the event that you may have seen it, we have called return search(struct node*) four times. At the point when we return either the new node or NULL, the value gets returned again and again until search(root) returns the eventual outcome.
On the off chance that the value isn’t discovered, we, in the end, arrive at the left or right child of a leaf node which is NULL and it gets propagated and returned.
Insert Operation
Inserting a value in the correct position is like looking since we attempt to keep up the standard that the left subtree is lesser than the root and the right subtree is larger than root.
We continue to go to either right subtree or left subtree relying upon the value and when we arrive at a point left or right subtree is null, we put the new node there.
Algorithm:
If node == NULL return createNode(data) if (data < node->data) node->left = insert(node->left, data); else if (data > node->data) node->right = insert(node->right, data); return node;
The algorithm isn’t pretty much as basic as it looks. Let’s attempt to visualize how we add a number to a current BST.
We have joined the node however we actually need to exit from the function without doing any damage to the rest of the tree. This is the place where the return node; toward the end proves to be useful. In the case of NULL, the recently created node is returned and connected to the parent node, in any case, a similar node is returned with no change as we go up until we get back to the root.
This ensures that as we move back up the tree, the other node associations aren’t changed.
Deletion Operation
There are three cases for erasing a node from a paired pursuit tree.
Case I
In the first case, the node to be erased is the leaf node. In such a case, essentially erase the node from the tree.
Case II
In the subsequent case, the node to be erased lies has a single child node. In such a case follow the steps underneath:
- Replace that node with its child node.
- Eliminate the child node from its original position.
Case III
In the third case, the node to be erased has two children. In such a case follow the steps underneath:
- Get the inorder successor of that node.
- Replace the node with the inorder successor.
- Eliminate the inorder successor from its original position.
Python, Java and C/C++ Examples
Python
# Binary Search Tree operations in Python # Create a node class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Inorder traversal def inorder(root): if root is not None: # Traverse left inorder(root.left) # Traverse root print(str(root.key) + "->", end=' ') # Traverse right inorder(root.right) # Insert a node def insert(node, key): # Return a new node if the tree is empty if node is None: return Node(key) # Traverse to the right place and insert the node if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) return node # Find the inorder successor def minValueNode(node): current = node # Find the leftmost leaf while(current.left is not None): current = current.left return current # Deleting a node def deleteNode(root, key): # Return if the tree is empty if root is None: return root # Find the node to be deleted if key < root.key: root.left = deleteNode(root.left, key) elif(key > root.key): root.right = deleteNode(root.right, key) else: # If the node is with only one child or no child if root.left is None: temp = root.right root = None return temp elif root.right is None: temp = root.left root = None return temp # If the node has two children, # place the inorder successor in position of the node to be deleted temp = minValueNode(root.right) root.key = temp.key # Delete the inorder successor root.right = deleteNode(root.right, temp.key) return root root = None root = insert(root, 8) root = insert(root, 3) root = insert(root, 1) root = insert(root, 6) root = insert(root, 7) root = insert(root, 10) root = insert(root, 14) root = insert(root, 4) print("Inorder traversal: ", end=' ') inorder(root) print("\nDelete 10") root = deleteNode(root, 10) print("Inorder traversal: ", end=' ') inorder(root)
Java
// Binary Search Tree operations in Java 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); } // Insert key in the tree Node insertKey(Node root, int key) { // Return a new node if the tree is empty if (root == null) { root = new Node(key); return root; } // Traverse to the right place and insert the node 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); } // Inorder Traversal 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) { // Return if the tree is empty if (root == null) return root; // Find the node to be deleted if (key < root.key) root.left = deleteRec(root.left, key); else if (key > root.key) root.right = deleteRec(root.right, key); else { // If the node is with only one child or no child if (root.left == null) return root.right; else if (root.right == null) return root.left; // If the node has two children // Place the inorder successor in position of the node to be deleted root.key = minValue(root.right); // Delete the inorder successor root.right = deleteRec(root.right, root.key); } return root; } // Find the inorder successor int minValue(Node root) { int minv = root.key; while (root.left != null) { minv = root.left.key; root = root.left; } return minv; } // Driver Program to test above functions 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(); } }
C
// Binary Search Tree operations in C #include <stdio.h> #include <stdlib.h> struct node { int key; struct node *left, *right; }; // Create a node struct node *newNode(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Inorder Traversal void inorder(struct node *root) { if (root != NULL) { // Traverse left inorder(root->left); // Traverse root printf("%d -> ", root->key); // Traverse right inorder(root->right); } } // Insert a node struct node *insert(struct node *node, int key) { // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } // Find the inorder successor struct node *minValueNode(struct node *node) { struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; } // Deleting a node struct node *deleteNode(struct node *root, int key) { // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { // If the node is with only one child or no child 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; } // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in the position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root; } // Driver code int main() { struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); printf("Inorder traversal: "); inorder(root); printf("\nAfter deleting 10\n"); root = deleteNode(root, 10); printf("Inorder traversal: "); inorder(root); }
c++
// Binary Search Tree operations in C++ #include <iostream> using namespace std; struct node { int key; struct node *left, *right; }; // Create a node struct node *newNode(int item) { struct node *temp = (struct node *)malloc(sizeof(struct node)); temp->key = item; temp->left = temp->right = NULL; return temp; } // Inorder Traversal void inorder(struct node *root) { if (root != NULL) { // Traverse left inorder(root->left); // Traverse root cout << root->key << " -> "; // Traverse right inorder(root->right); } } // Insert a node struct node *insert(struct node *node, int key) { // Return a new node if the tree is empty if (node == NULL) return newNode(key); // Traverse to the right place and insert the node if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); return node; } // Find the inorder successor struct node *minValueNode(struct node *node) { struct node *current = node; // Find the leftmost leaf while (current && current->left != NULL) current = current->left; return current; } // Deleting a node struct node *deleteNode(struct node *root, int key) { // Return if the tree is empty if (root == NULL) return root; // Find the node to be deleted if (key < root->key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { // If the node is with only one child or no child 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; } // If the node has two children struct node *temp = minValueNode(root->right); // Place the inorder successor in the position of the node to be deleted root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } return root; } // Driver code int main() { struct node *root = NULL; root = insert(root, 8); root = insert(root, 3); root = insert(root, 1); root = insert(root, 6); root = insert(root, 7); root = insert(root, 10); root = insert(root, 14); root = insert(root, 4); cout << "Inorder traversal: "; inorder(root); cout << "\nAfter deleting 10\n"; root = deleteNode(root, 10); cout << "Inorder traversal: "; inorder(root); }
Binary Search Tree Complexities
Time Complexity
Operation | Best Case Complexity | Average Case Complexity | Worst Case Complexity |
Search | 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) |
Here, n is the number of nodes in the tree.
Space Complexity
The space complexity for all the operations is O(n).
Binary Search Tree Applications
- In multilevel indexing in the database
- For dynamic sorting
- For managing virtual memory areas in Unix kernel
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.