Python Program to Construct a Binary Search Tree and Perform Deletion and Inorder Traversal

This is a Python program to construct a binary search tree and perform deletion and inorder traversal.

Problem Description

The program creates a binary search tree and presents a menu to the user to perform insertion, deletion and inorder traversal operations.

Problem Solution

1. Create a class BSTNode with instance variables key, left, right and parent.
2. Define methods insert, inorder, replace_node_of_parent, find_min, remove and search in BSTNode.
3. The method insert takes a node as argument and inserts that node in the BST with the BSTNode object as root.
4. The method inorder displays the inorder traversal of the BST with the BSTNode object as root.
5. The method replace_node_of_parent takes a node as argument and replaces the current object in the BST with the node.
6. The method find_min finds the the left-most node in the BST with the BSTNode object as root.
7. The method remove removes the current BSTNode object from the BST.
8. The method search takes a key as argument and returns the node with that key in the BST with the BSTNode object as root.
9. Create a class BSTree with instance variable root.
10. Define methods inorder, add, remove and search in BSTree.
11. The method inorder calls the inorder method of the root node.
12. The method add takes a key as argument and adds a node with that key by calling the insert method of the root node.
13. The method search takes a key as argument and returns the node with that key by calling the search method of the root node.
14. The method remove takes a key as argument and removes the node with that key. If the node is the root node then the instance variable root is set to None otherwise the remove method of the node is called.

Program/Source Code

Here is the source code of a Python program to implement a binary search tree and perform deletion and inorder traversal operations. The program output is shown below.

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None
 
    def insert(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert(node)
        elif self.key < node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert(node)
 
    def inorder(self):
        if self.left is not None:
            self.left.inorder()
        print(self.key, end=' ')
        if self.right is not None:
            self.right.inorder()
 
    def replace_node_of_parent(self, new_node):
        if self.parent is not None:
            if new_node is not None:
                new_node.parent = self.parent
            if self.parent.left == self:
                self.parent.left = new_node
            elif self.parent.right == self:
                self.parent.right = new_node
        else:
            self.key = new_node.key
            self.left = new_node.left
            self.right = new_node.right
            if new_node.left is not None:
                new_node.left.parent = self
            if new_node.right is not None:
                new_node.right.parent = self
 
    def find_min(self):
        current = self
        while current.left is not None:
            current = current.left
        return current
 
    def remove(self):
        if (self.left is not None and self.right is not None):
            successor = self.right.find_min()
            self.key = successor.key
            successor.remove()
        elif self.left is not None:
            self.replace_node_of_parent(self.left)
        elif self.right is not None:
            self.replace_node_of_parent(self.right)
        else:
            self.replace_node_of_parent(None)
 
    def search(self, key):
        if self.key > key:
            if self.left is not None:
                return self.left.search(key)
            else:
                return None
        elif self.key < key:
            if self.right is not None:
                return self.right.search(key)
            else:
                return None
        return self
 
 
class BSTree:
    def __init__(self):
        self.root = None
 
    def inorder(self):
        if self.root is not None:
            self.root.inorder()
 
    def add(self, key):
        new_node = BSTNode(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert(new_node)
 
    def remove(self, key):
        to_remove = self.search(key)
        if (self.root == to_remove
            and self.root.left is None and self.root.right is None):
            self.root = None
        else:
            to_remove.remove()
 
    def search(self, key):
        if self.root is not None:
            return self.root.search(key)
 
 
bstree = BSTree()
 
print('Menu (this assumes no duplicate keys)')
print('add <key>')
print('remove <key>')
print('inorder')
print('quit')
 
while True:
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'add':
        key = int(do[1])
        bstree.add(key)
    elif operation == 'remove':
        key = int(do[1])
        bstree.remove(key)
    elif operation == 'inorder':
        print('Inorder traversal: ', end='')
        bstree.inorder()
        print()
    elif operation == 'quit':
        break

Program Explanation

1. An instance of BSTree is created.
2. The user is presented with a menu to perform insertion, deletion and inorder traversal on the tree.
3. The corresponding methods are called to perform each operation.

Note: Join free Sanfoundry classes at Telegram or Youtube

Runtime Test Cases

Case 1:
Menu (this assumes no duplicate keys)
add <key>
remove <key>
inorder
quit
What would you like to do? add 5
What would you like to do? add 1
What would you like to do? add 10
What would you like to do? add 7
What would you like to do? add 3
What would you like to do? inorder
Inorder traversal: 1 3 5 7 10 
What would you like to do? remove 3
What would you like to do? remove 7
What would you like to do? inorder
Inorder traversal: 1 5 10 
What would you like to do? remove 5
What would you like to do? inorder
Inorder traversal: 1 10 
What would you like to do? quit
 
Case 2:
Menu (this assumes no duplicate keys)
add <key>
remove <key>
inorder
quit
What would you like to do? add 2
What would you like to do? add 8
What would you like to do? inorder
Inorder traversal: 2 8 
What would you like to do? add 5
What would you like to do? inorder
Inorder traversal: 2 5 8 
What would you like to do? remove 2
What would you like to do? remove 8
What would you like to do? inorder
Inorder traversal: 5 
What would you like to do? remove 5
What would you like to do? inorder
Inorder traversal: 
What would you like to do? quit

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.