Deletion in Binary Search Tree in Python
Deleting a node in Binary search tree involves deleting an existing node while maintaining the properties of Binary Search Tree(BST). we need to search the node which needs to be deleted and then delete it.
Case 1 : While deleting a node having both left child and right child
- After finding the node to be deleted, copy the value of right child to v and copy the right child’s left pointer to left of v and right pointer
- In the above example, suppose we need to delete 18 then we need to replace 18 with the maximum value of its left or right sub tree
- Let us replace it with 20 which is maximum value of right sub tree
- So after deleting 18, the Binary search tree looks like this
Case 2 : While deleting a node having either left child or right child
- After finding the node to be deleted, we need to replace the value in the node with its left node it has left child or right node if it has right child.
- In the above example, suppose we need to delete 16 then we need to replace 16 with the value of its right child node
- So it will be replaced with 17 which is the value of its right child node
- So after deleting 16, the Binary search tree looks like this
Case 3 : While deleting a leaf node(a node which has no child)
- In the above example, suppose we need to delete 4 which is a leaf node.
- Simply we change value of the node, left and right pointers to None.
- After deleting 4 the BST looks like this:
Deletion in Binary Search Tree in Python
class Tree:
def __init__(self, val=None):
# Initialize the Tree node with a value
self.value = val
# Create left and right child nodes
#if the value is not None
if self.value:
self.left = Tree()
self.right = Tree()
else:
self.left = None
self.right = None
def isempty(self):
# Check if the node is empty (value is None)
return (self.value == None)
def insert(self, data):
# Insert a new value into the Tree
if self.isempty():
self.value = data
self.left = Tree()
self.right = Tree()
elif self.value == data:
return
elif data < self.value:
self.left.insert(data)
return
elif data > self.value:
self.right.insert(data)
return
def isleaf(self):
# Check if the node is a leaf node (no children)
if self.left == None and self.right == None:
return True
else:
return False
def maxval(self):
# Find the maximum value in the Tree
if self.right.right == None:
return (self.value)
else:
return (self.right.maxval())
def delete(self, v):
# Delete a value from the Tree
if self.isempty():
return
if v < self.value:
self.left.delete(v)
return
if v > self.value:
self.right.delete(v)
return
if v == self.value:
if self.isleaf():
self.value = None
self.left = None
self.right = None
return
elif self.left.isempty():
self.value = self.right.value
self.left = self.right.left
self.right = self.right.right
return
else:
self.value = self.left.maxval()
self.left.delete(self.left.maxval())
return
def inorder(self):
# Traverse the Tree in inorder (left-root-right)
#and return the values
if self.isempty():
return ([])
else:
return (self.left.inorder() + [self.value] + self.right.inorder())
# Test the Tree class
t = Tree(15)
t.insert(10)
t.insert(18)
t.insert(4)
t.insert(11)
t.insert(16)
t.insert(20)
print("Before deleting 4: ")
print(t.inorder())
t.delete(4)
print("After deleting 4: ")
print(t.inorder())
Output
Before deleting 4: [4, 10, 11, 15, 16, 18, 20] After deleting 4: [10, 11, 15, 16, 18, 20]
Time complexity: O(log n)
Space complexity: O(1)
Binary Search Tree In Python
A Binary search tree is a binary tree where the values of the left sub-tree are less than the root node and the values of the right sub-tree are greater than the value of the root node. In this article, we will discuss the binary search tree in Python.