Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
Hey Ninjas, today we will read about a popular data structure, binary tree. It has a wide range of applications throughout various fields. Thus, it is also important when it comes to interviews with top tech companies. A mastery of binary trees could help us solve a lot of problems. In this article, we will be focusing on binary search trees.
What is a binary search tree?
A binary search tree (BST) is a data structure in which each node has at most two child nodes, left and right. The left child node holds a value less than or equal to its parent node, and the right child node holds a value greater than the parent node. This ordering property allows for efficient searching, insertion, and deletion of elements in the tree.
In this article, we will look at one problem based on this data structure.
Problem Statement
We are given a binary search tree and also a node. The task is to delete the node from the binary search tree iteratively.
Recommended: Try this problem yourself before moving on to the solution.
Example
Input
Let the BST be 2, 3, 4, 5, 6, 7 (Inorder Traversal).
You have to delete 3 from the BST. What will be the remaining BST?
Output
The In-order traversal of the remaining BST will be 2, 4, 5, 6, 7.
Approach
There are some specific cases we have to handle while deleting the node in the binary search tree, so let's explore all the different cases:
Case 1: If we have to delete a node that is a leaf node, then we can simply delete that node.
Case 2: If we have to delete a node that has only one child. In this case, we simply swap the value of the child node with the current node and delete the child node, which is a leaf node.
Case 3: If we have to delete a node with both children or an internal node. In that situation, first, we have to find the node's in-order successor. After this, we have to copy the value of the node's in-order successor to that particular node. Then we have to delete the in-order successor node. We can find the in-order successor for any element just by seeing the minimum element in the right subtree of that element.
Algorithm
Check if the value to be deleted is present in the binary search tree.
If the value is present in the binary search tree, check the number of children the node to be deleted has.
If the node to be deleted has either one child or 0 children, then use the following steps:
Make a new pointer of the tree node named as a new tree node that will replace the node to be deleted.
Check if the current node left child exists, then assign the new tree node pointer to the left of the current else, assign it to the right of the current.
Now check whether the node to be deleted is the root, then return the new tree node from the function.
Now check which side of the previous the current node is attached. If it is attached to the left of the previous, then assign a new tree node to the left of the previous. Otherwise, to the right of the previous and last, delete the current.
If the node is to be deleted has two child nodes, then use the following steps to delete the node:
Compute the in-order successor for the node to be deleted
Before replacing the value, check if the parent node of the in-order successor is the current node or not. If it is not, then make the left child of the parent equal to the in-order successor of the right child.
Else, if the inorder successor was itself the current, then make the right child of the node to be deleted equal to the right child of the inorder successor.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
node(int data){
this->data = data;
left = nullptr;
right = nullptr;
}
};
// Printing the nodes of tree using inorder traversal
void inorder(node *root){
if (root != NULL){
inorder(root->left);
cout << root->data << ' ';
inorder(root->right);
}
}
// A new node insertion in binary search tree
node *insert(node *root, int key){
// Check if the tree is null or empty then simply return the root value
if (root == NULL){
node *temp = new node(key);
return temp;
}
if (key < root->data){
/*
If the key is less than root_data we have to insert the element
in left subtree for that we will simply call the recursion in left
subtree part
*/
root->left = insert(root->left, key);
}
else{
/*
If the key is greater than root_data we have to insert the element
in right subtree for that we will simply call the recursion in right
subtree part
*/
root->right = insert(root->right, key);
}
return root;
}
node *deleteNode(node *root, int value){
// Current pointer to iterate
node *stat = root;
// One previous pointer from current
node *prev = NULL;
/*
Iterating in binary search tree to check if the key with value
data is actually present there or not
*/
while (stat != NULL && stat->data != value){
prev = stat;
if (value < stat->data)
stat = stat->left;
else
stat = stat->right;
}
if (stat == NULL){
cout << "Value not found in BST" << endl;
return root;
}
// Check if the node to be deleted has either 0 or 1 child
if (stat->left == NULL || stat->right == NULL){
// newtreenode with store the node to be deleted
node *newtreenode;
// check whether the node to be deleted has either 0 or 1 child
if (stat->left == NULL)
newtreenode = stat->right;
else
newtreenode = stat->left;
/*
check whether the node to be deleted is the root then simply return newtreenode
*/
if (prev == NULL)
return newtreenode;
/*
check the node to be deleted is whether the previous nodes left or right and
replace it with the newtreenode
*/
if (stat == prev->left)
prev->left = newtreenode;
else
prev->right = newtreenode;
// simply delete the node
delete stat;
}
// here node which has to be deleted has 2 child nodes
else{
node *prev = NULL;
node *temp;
// finding the inorder successor in case of node with 2 child nodes
temp = stat->right;
while (temp->left != NULL)
{
prev = temp;
temp = temp->left;
}
/*
before replacing the value check if the parent node of the inorder successor
is the current node or not if it is not then make the left child of the parent
equal to the inorder successor of the right child else if inorder successor was
itself the current then make the right child of the node to be deleted equal
To the right child of inorder successor
*/
prev != NULL ? prev->left = temp->right : stat->right = temp->right;
stat->data = temp->data;
delete temp;
}
return root;
}
int main()
{
node *root = NULL;
root = insert(root, 5);
root = insert(root, 3);
root = insert(root, 2);
root = insert(root, 4);
root = insert(root, 6);
root = insert(root, 7);
cout << "Inorder traversal of original BST";
cout << endl;
inorder(root);
cout << endl;
// deleting the node having value as 3
deleteNode(root, 3);
cout << "Inorder traversal of new tree after deletion";
cout << endl;
inorder(root);
cout << endl;
return 0;
}
You can also try this code with Online C++ Compiler
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Printing the nodes of tree using inorder traversal
def inorder(root):
if root != None:
inorder(root.left)
print(root.data, end=" ")
inorder(root.right)
# A new node insertion in binary search tree
def insert(root, key):
if root == None:
return Node(key)
if key < root.data:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
# First we will be Iterating in binary search tree to
# check if the key with value data is actually present
# there or not. Then we will check the number of children
# of the node and work accordingly
def deleteNode(root, value):
if root == None:
print("Value not found in BST")
return root
if value < root.data:
root.left = deleteNode(root.left, value)
elif value > root.data:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
return temp
elif root.right == None:
temp = root.left
return temp
temp = minValueNode(root.right)
root.data = temp.data
root.right = deleteNode(root.right, temp.data)
return root
def minValueNode(node):
current = node
while(current.left != None):
current = current.left
return current
def main():
root = None
root = insert(root, 5)
root = insert(root, 3)
root = insert(root, 2)
root = insert(root, 4)
root = insert(root, 6)
root = insert(root, 7)
print("Inorder traversal of the given tree")
inorder(root)
# deleting node having value 3
root = deleteNode(root, 3)
print("Inorder traversal of the modified tree")
inorder(root)
if __name__ == '__main__':
main()
You can also try this code with Online Java Compiler
The time complexity is O(N). Deleting a node in the Binary search tree using the iterative method will cost O(N) time complexity, where ‘N’ is the number of nodes in the binary search tree. Since we are iterating only once on every node, it will cost linear time complexity.
Space Complexity
The space complexity for deleting a node in the Binary search tree using the iterative method will cost O(1). The reason behind this is we are not using extra space.
Binary search trees (BSTs) are a type of data structure that can be used to efficiently store and retrieve data. They are commonly used in various applications, such as:
Searching for specific data in a large dataset: Because BSTs are organized in a way that allows for fast searching, they are often used to find specific data within a large dataset quickly.
Sorting data: By repeatedly removing the smallest (or largest) element from a BST, the data stored in the tree can be sorted in ascending (or descending) order.
Implementing dictionaries and sets: BSTs can be used to implement dictionaries and sets, where each element is stored as a key-value pair or just a key.
In databases, it is used as an indexing method.
In computer file systems, it is used as a method of organizing files and folders.
In some game development, it is used for pathfinding in games.
Overall, binary search trees are a powerful and efficient data structure that can be used to solve a wide variety of problems.
A binary tree is a data structure where each node can have at most two child nodes (left and right). The topmost node is the root, and the leaf nodes have no children.
What is a binary search tree?
A binary search tree (BST) is a type of binary tree where each node has at most two child nodes. The key in each node must be greater than or equal to any key stored in its left sub-tree and less than or equal to any key stored in its right sub-tree.
What is the time complexity for deleting a node in a binary search tree?
The time complexity for deleting a node in a binary search tree is O(N).
What is the space complexity for deleting a node in a binary search tree?
The space complexity for deleting a node in a binary search tree is O(1).
Is there any other way also to solve this problem?
Yes, we can solve this problem using recursion also. The difference between the two approaches is that in the iterative approach, the space complexity is O(1), whereas in the recursive approach, it is O(N).
Conclusion
In this article, we learned the iterative method for deleting a node in a BST. We learned about the intuition and approach for this algorithm. We also learned about its implementation in popular programming languages and their complexity analysis.
Check out our articles if you think this blog has helped you enhance your knowledge and want to learn more. Visit our website to read more such blogs.