How to delete a node from a Binary Search Tree in Python?

In this article, we will look at how to delete a node from a Binary Search tree in Python. It is likely that you know what a binary search tree is, however, let’s go through a short explanation. This article will contain a short description of a binary search tree, code to create a binary search tree and to delete a node from the Binary Search Tree.

Binary Search Tree

The following are the properties of a Binary Search Tree.

• A binary search tree is a rooted tree where each node can have at most 2 child nodes namely – left child and the right child.
• The value of the left child must be smaller than that of the root node.
• The value of the right child must be larger than that of the root node.
• Finally, all the values in the Binary Search tree must be unique.

Creating a BST

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, current_node, value):
        if current_node == None:
            current_node = Node(value)
        elif value < current_node.value:
            current_node.left = self.insert(current_node.left, value)
        else:
            current_node.right = self.insert(current_node.right, value)
        return current_node

n = int(input())
arr = list(map(int, input().split()))

# Choose a root node
root = Node(arr[0])
for value in arr[1:]:
    root.insert(root, value)

With the above code, we can create a Binary Search Tree so let’s now move on to the main part, how to delete a node from a binary search tree.

Python program to delete a node from a Binary Search Tree

The node to be deleted falls under one of the three categories:

1. is a leaf node
2. has one child
3. has 2 children

1. The node to be deleted is a leaf node:

If the node to be deleted is a leaf node, deleting the node alone is enough and no additional changes are needed.

2. The node to be deleted has one child:

Copy the contents of the one-child to the current node and delete the child and no other modifications are needed.

3. The node to be deleted has 2 children: 

Find the smallest node in the right subtree of the current node which is also called the inorder successor and replace the current node with it which instead can be done with the inorder predecessor and the changes would be valid.

Let’s see the implementation of the same:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, current_node, value):
        if current_node == None:
            current_node = Node(value)
        elif value < current_node.value:
            current_node.left = self.insert(current_node.left, value)
        else:
            current_node.right = self.insert(current_node.right, value)
        return current_node

    # To find the inorder successor which is the smallest node in the subtree
    def findsuccessor(self, current_node):
        while current_node.left != None:
            current_node = current_node.left
        return current_node

    def delete(self, current_node, value):
        if current_node == None:
            return current_node
        if value == current_node.value:
            
            if current_node.left == None:
                current_node = current_node.right
            elif current_node.right == None:
                current_node = current_node.left
            else:
                # deletion of nodes with 2 children
                # find the inorder successor and replace the current node
                current_node = findsuccessor(current_node)
                current_node.right = delete(current_node.right, current_node.value)
        elif value < current_node.value:
            current_node.left = self.delete(current_node.left, value)
        else:
            current_node.right = self.delete(current_node.right, value)

        return current_node

Now let’s try to test the code:

n = int(input())
arr = list(map(int, input().split()))

# Choose a root node
root = Node(arr[0])
for value in arr[1:]:
    root.insert(root, value)

delete_val = int(input("Enter the value to be deleted"))
root = root.delete(root, delete_val)
print("The value of the root is", root.value)

For example, let’s delete the root node for the tree created for the values 5, 1, 2, 4, 3, here the root node is 5 whose deletion will bring the inorder successor 4 to the root.

5
5 1 2 4 3
5

The output for the above input would be:

The value of the root is 4

Therefore, I hope you found this article helpful in understanding how to delete a node from a Binary Search Tree in Python.

See also:

• Build a balanced BST from a sorted array

2 responses to “How to delete a node from a Binary Search Tree in Python?”

1. chirag shetty says:

   April 19, 2021 at 10:29 pm

   by returning the value it’s not deleting the value?

   Reply
2. S. Lakshmana Pandian says:

   August 11, 2021 at 5:50 pm

   Not correct the delete part of this code

   Reply