Binary Search Tree (BST)

Question

You're tasked with implementing various operations on a binary search tree (BST). The BST will store integers, and you need to implement methods for insertion, deletion, and finding the minimum and maximum values. Check out the Hint button if you need more information about the BST.
class BinarySearchTree:
    def __init__(self):
        pass
    
    def insert(self, value: int):
        pass
    
    def delete(self, value: int):
        pass
    
    def find_min(self) -> int:
        pass
    
    def find_max(self) -> int:
        pass
Methods

 	insert(value: int): Inserts a new node with the given integer value into the BST.
 	delete(value: int): Deletes a node with the given integer value from the BST. If the value doesn't exist, do nothing.
 	find_min() -> int: Returns the minimum integer value stored in the BST.
 	find_max() -> int: Returns the maximum integer value stored in the BST.

Note

 	Implement the BST from scratch; do not use built-in data structures that behave like a BST.
 	All integers in the BST need to be unique.

Example
example_bst = BinarySearchTree()

# Insert elements to build the tree
values_to_insert = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for value in values_to_insert:
    example_bst.insert(value)

print(example_bst.find_min())  # Should return 1
print(example_bst.find_max())  # Should return 14
example_bst.delete(1)
print(example_bst.find_min())  # Should return 3

Accepted Answer

# Implementing the Binary Search Tree (BST) class with various operations class Node: def __init__(self, value): self.value = value self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None # Insert a new value into the BST def insert(self, value): self.root = self._insert(self.root, value) def _insert(self, node, value): if not node: return Node(value) if value < node.value: node.left = self._insert(node.left, value) elif value > node.value: node.right = self._insert(node.right, value) return node # Delete a value from the BST def delete(self, value): self.root = self._delete(self.root, value) def _delete(self, node, value): if not node: return None if value < node.value: node.left = self._delete(node.left, value) elif value > node.value: node.right = self._delete(node.right, value) else: if not node.left: return node.right if not node.right: return node.left min_larger_node = self._get_min(node.right) node.value = min_larger_node.value node.right = self._delete(node.right, min_larger_node.value) return node # Find the minimum value in the BST def find_min(self): min_node = self._get_min(self.root) return min_node.value if min_node else None def _get_min(self, node): current = node while current.left: current = current.left return current # Find the maximum value in the BST def find_max(self): max_node = self._get_max(self.root) return max_node.value if max_node else None def _get_max(self, node): current = node while current.right: current = current.right return current # Let's use the BinarySearchTree class to create the example tree # Initialize the tree example_bst = BinarySearchTree() # Insert elements to build the tree values_to_insert = [8, 3, 10, 1, 6, 14, 4, 7, 13] for value in values_to_insert: example_bst.insert(value) print(example_bst.find_min()) # Should return 1 print(example_bst.find_max()) # Should return 14 example_bst.delete(1) print(example_bst.find_min()) # Should return 3

Title	Category	Subcategory	Difficulty	Status
All Pairs	Programming	Array and List Processing	Easy	Example
Arithmetic Mean	Programming	Array and List Processing	Hard	Unlock
Find the Missing Number	Programming	Array and List Processing	Easy	Unlock
Finding the Largest Possible Number	Programming	Array and List Processing	Easy	Unlock
Longest Common Subsequence (LCS)	Programming	Array and List Processing	Medium	Example
Sorting Without Sort()	Programming	Array and List Processing	Hard	Unlock
Subarray Sum Equals Zero	Programming	Array and List Processing	Medium	Unlock
Sudoku	Programming	Array and List Processing	Hard	Unlock

The Interview Guide for Quants and Traders