'''
inorder()function time complexity : O(n)
insert() function time complexity : O(n)
delete() function time complexity : O(n)
'''
# Python program to delete operation
# in binary search tree(BST)
# A Binary Tree Node
class Node:
# Constructor to create a new node
def __init__(self, key):
self.val = key
self.left = None
self.right = None
# A function to do inorder traversal
def inorder(root):
if root is not None:
inorder(root.left)
print(root.val, end=' ')
inorder(root.right)
# A function to insert a new node
def insert(root, key):
# if the tree is empty, return a new node
if root is None:
return Node(key)
# otherwise recur down the tree
if root.val < key:
root.right = insert(root.right, key)
else:
root.left = insert(root.left, key)
return root
# A function min key value found in that tree
def minValueNode(root):
while root.left is not None:
root = root.left
return root
# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):
# Base case
if root is None:
return root
# if the key to be deleted is smaller than the root's
# key then it lies in left subtree
if root.val > key:
root.left = deleteNode(root.left, key)
# if the key to be delete is greater then the root's key
# then it lies in right subtree
elif root.val < key:
root.right = deleteNode(root.right, key)
else:
# Node with only 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
# Node with two children Get teh inorder successor
# smallest in the right subtree
temp = minValueNode(root.right)
# Copy the inorder successor's content to this node
root.val = temp.val
# Delete the inorder successor
root.right = deleteNode(root.right, temp.val)
return root
# Driver program to test above functions
if __name__ == '__main__':
""" Let us create following BST
50
/
30 70
/ /
20 40 60 80
/
55
inorder traversal->[20, 30, 40, 50, 55, 60, 70, 80]
"""
root = None
root = insert(root, 80)
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 55)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
print("Inorder traversal of the given tree")
inorder(root)
print("
Delete->50")
root = deleteNode(root, 50)
print("Inorder traversal of the modified tree")
inorder(root)
print("
Delete->20")
root = deleteNode(root, 20)
print("Inorder traversal of the modified tree")
inorder(root)
print("
Delete->30")
root = deleteNode(root, 70)
print("Inorder traversal of the modified tree")
inorder(root)
// C++ program to demonstrate
// delete operation in binary
// search tree
#include <bits/stdc++.h>
using namespace std;
struct node {
int key;
struct node *left, *right;
};
// A utility function to create a new BST 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;
}
// A utility function to do
// inorder traversal of BST
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left);
cout << root->key;
inorder(root->right);
}
}
/* A utility function to
insert a new node with given key in
* BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree, return the node
with minimum key value found in that tree. Note that the
entire tree does not need to be searched. */
struct node* minValueNode(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current && current->left != NULL)
current = current->left;
return current;
}
/* Given a binary search tree and a key, this function
deletes the key and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
// base case
if (root == NULL)
return root;
// If the key to be deleted is
// smaller than the root's
// key, then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);
// If the key to be deleted is
// greater than the root's
// key, then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);
// if key is same as root's key, 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 only one child or no child
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;
}
// node with two children: Get the inorder successor
// (smallest in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Driver Code
int main()
{
/* Let us create following BST
50
/
30 70
/ /
20 40 60 80 */
struct node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout << "Inorder traversal of the given tree
";
inorder(root);
cout << "
Delete 20
";
root = deleteNode(root, 20);
cout << "Inorder traversal of the modified tree
";
inorder(root);
cout << "
Delete 30
";
root = deleteNode(root, 30);
cout << "Inorder traversal of the modified tree
";
inorder(root);
cout << "
Delete 50
";
root = deleteNode(root, 50);
cout << "Inorder traversal of the modified tree
";
inorder(root);
return 0;
}
// This code is contributed by shivanisinghss2110