This is a Python program to construct a binary search tree and perform deletion and inorder traversal.
The program creates a binary search tree and presents a menu to the user to perform insertion, deletion and inorder traversal operations.
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.
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
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.
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.
- Practice Programming MCQs
- Check Python Books
- Apply for Python Internship
- Apply for Programming Internship
- Check Information Technology Books
