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__.