How would you design and implement a binary search tree class from scratch, including methods for insert, find, delete, and a getRandomNode() method that returns a random node with equal probability? Please explain your approach for implementing each method

Approach To design and implement a binary search tree (BST) class from scratch, we will follow a structured framework that includes: Defining the Tree Node Structure Create a class for the nodes of the tree. Each node will hold a value, pointers to left and…

Approach

To design and implement a binary search tree (BST) class from scratch, we will follow a structured framework that includes:

1. Defining the Tree Node Structure

• Create a class for the nodes of the tree.
• Each node will hold a value, pointers to left and right children, and maintain a count of nodes for random selection.
• Implementing the Binary Search Tree Class
• Create a class for the BST.
• Implement methods for insertion, searching, deletion, and retrieving a random node.
• Detailing Each Method's Functionality
• Break down the logic of each method to ensure clarity and efficiency.

Key Points

• Understand the BST Properties: A binary search tree maintains order; for any node, values in the left subtree are less, and values in the right subtree are greater.
• Insertion Logic: Properly placing the new node while maintaining the order.
• Search Logic: Efficiently locating a node based on value comparisons.
• Deletion Logic: Handling three cases—leaf node, node with one child, and node with two children.
• Random Node Selection: Utilizing the size of the tree to select a node uniformly at random.

Standard Response

Here's a detailed example of how to implement a BST class in Python, including the essential methods.

import random

class TreeNode:
 def __init__(self, key):
 self.left = None
 self.right = None
 self.val = key
 self.size = 1 # To keep track of the size of the subtree

class BinarySearchTree:
 def __init__(self):
 self.root = None

 def insert(self, key):
 if not self.root:
 self.root = TreeNode(key)
 else:
 self._insert_rec(self.root, key)

 def _insert_rec(self, node, key):
 if key < node.val:
 if node.left is None:
 node.left = TreeNode(key)
 else:
 self._insert_rec(node.left, key)
 else: # key >= node.val
 if node.right is None:
 node.right = TreeNode(key)
 else:
 self._insert_rec(node.right, key)
 node.size += 1 # Increment the size of the current node's subtree

 def find(self, key):
 return self._find_rec(self.root, key)

 def _find_rec(self, node, key):
 if node is None or node.val == key:
 return node
 if key < node.val:
 return self._find_rec(node.left, key)
 return self._find_rec(node.right, key)

 def delete(self, key):
 self.root = self._delete_rec(self.root, key)

 def _delete_rec(self, node, key):
 if node is None:
 return node
 if key < node.val:
 node.left = self._delete_rec(node.left, key)
 elif key > node.val:
 node.right = self._delete_rec(node.right, key)
 else:
 # Node with only one child or no child
 if node.left is None:
 return node.right
 elif node.right is None:
 return node.left
 
 # Node with two children: get the inorder successor
 temp = self._min_value_node(node.right)
 node.val = temp.val
 node.right = self._delete_rec(node.right, temp.val)
 
 node.size -= 1 # Decrement the size of the current node's subtree
 return node

 def _min_value_node(self, node):
 current = node
 while current.left is not None:
 current = current.left
 return current

 def getRandomNode(self):
 if not self.root:
 return None
 return self._getRandomNode_rec(self.root)

 def _getRandomNode_rec(self, node):
 if node is None:
 return None
 left_size = node.left.size if node.left else 0
 index = random.randint(0, node.size - 1)
 if index < left_size:
 return self._getRandomNode_rec(node.left)
 elif index == left_size:
 return node
 else:
 return self._getRandomNode_rec(node.right)

# Example Usage
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)
print(bst.find(3).val) # Output: 3
bst.delete(3)
print(bst.find(3)) # Output: None
print(bst.getRandomNode().val) # Randomly returns a node from the BST

Tips & Variations

Common