This is a Python program to find the smallest and largest elements in a binary search tree.
The program presents a menu to the user to perform various operations on a binary search tree including finding the smallest and largest elements.
1. Create a class BSTNode with instance variables key, left, right and parent.
2. Define methods insert 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 search takes a key as argument and returns the node with that key in the BST with the BSTNode object as root.
5. Create a class BSTree with instance variable root.
6. Define methods add, search, get_smallest and get_largest in BSTree.
7. The method add takes a key as argument and adds a node with that key by calling the insert method of the root node.
8. The method search takes a key as argument and returns the node with that key by calling the search method of the root node.
9. The method get_smallest returns the smallest node by returning the left-most node.
10. The method get_largest returns the largest node by returning the right-most node.
Here is the source code of a Python program to find the smallest and largest elements in a binary search tree. 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 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 add(self, key): new_node = BSTNode(key) if self.root is None: self.root = new_node else: self.root.insert(new_node) def search(self, key): if self.root is not None: return self.root.search(key) def get_smallest(self): if self.root is not None: current = self.root while current.left is not None: current = current.left return current.key def get_largest(self): if self.root is not None: current = self.root while current.right is not None: current = current.right return current.key bstree = BSTree() print('Menu (this assumes no duplicate keys)') print('add <key>') print('smallest') print('largest') 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) if operation == 'smallest': smallest = bstree.get_smallest() print('Smallest element: {}'.format(smallest)) if operation == 'largest': largest = bstree.get_largest() print('Largest element: {}'.format(largest)) elif operation == 'quit': break
1. An instance of BSTree is created.
2. The user is presented with a menu to perform various operations including finding the smallest and largest elements.
3. The corresponding methods are called to perform each operation.
Case 1: Menu (this assumes no duplicate keys) add <key> smallest largest quit What would you like to do? add 3 What would you like to do? add 2 What would you like to do? add 10 What would you like to do? add 4 What would you like to do? smallest Smallest element: 2 What would you like to do? largest Largest element: 10 What would you like to do? quit Case 2: Menu (this assumes no duplicate keys) add <key> smallest largest quit What would you like to do? add 10 What would you like to do? smallest Smallest element: 10 What would you like to do? largest Largest element: 10 What would you like to do? add 4 What would you like to do? add 12 What would you like to do? smallest Smallest element: 4 What would you like to do? largest Largest element: 12 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 Information Technology Books
- Check Python Books
- Apply for Python Internship
- Apply for Programming Internship
