# Python Program to Find Minimum and Maximum Element in Binary Search Tree

This is a Python program to find the smallest and largest elements in a binary search tree.

Problem Description

The program presents a menu to the user to perform various operations on a binary search tree including finding the smallest and largest elements.

Problem Solution

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.

Program/Source Code

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

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('smallest')
print('largest')
print('quit')

while True:
do = input('What would you like to do? ').split()

operation = do[0].strip().lower()
key = int(do[1])
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```
Program Explanation

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.

Runtime Test Cases
```Case 1:
Menu (this assumes no duplicate keys)
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)
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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

If you find any mistake above, kindly email to [email protected]