A binary search tree is a hierarchical data structure that allows for efficient insertion, deletion, and searching of elements.
The solution below defines a Binary Search Tree (BST) class and its methods to insert, search, and remove nodes from the tree.
At the core of it is the BST property: values less than the current node's value go to the left, and values greater than or equal to the current node's value go to the right.
What Problem is being Solved?
The BST class is solving the problem of creating and managing a binary search tree data structure.
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Average: O(log(n)) time | O(1) space
# Worst: O(n) time | O(1) space
def insert(self, value):
currentNode = self
while True:
if value < currentNode.value:
if currentNode.left is None:
currentNode.left =BST(value)
break
else:
currentNode = currentNode.left
else:
if currentNode.right is None:
currentNode.right =BST(value)
break
else:
currentNode= currentNode.right
return self
# Average: O(log(n)) time | O(1) space
# Worst: O(n) time | O(1) space
def contains(self, value):
currentNode=self
while currentNode is not None:
if value < currentNode.value:
currentNode = currentNode.left
elif value > currentNode.value:
currentNode = currentNode.right
else:
return True
return False
# Average: O(log(n)) time | O(1) space
# Worst: O(n) time | O(1) space
def remove(self, value, parentNode=None):
currentNode =self
while currentNode is not None:
if value < currentNode.value:
parentNode =currentNode
currentNode =currentNode.left
elif value > currentNode.value:
parentNode = currentNode
currentNode =currentNode.right
else:
if currentNode.left is not None and currentNode.right is not None:
currentNode.value =currentNode.getMinValue()
currentNode.right.remove(currentNode.value, currentNode)
elif parentNode is None:
if currentNode.left is not None:
currentNode.value = currentNode.left.value
currentNode.right = currentNode.left.right
currentNode.left = currentNode.left.left
elif currentNode.right is not None:
currentNode.value = currentNode.right.value
currentNode.left = currentNode.right.left
currentNode.right = currentNode.right.right
else:
currentNode.value =None
elif parentNode.left == currentNode:
parentNode.left = currentNode.left if currentNode.left is not None else currentNode.right
elif parentNode.right == currentNode:
parentNode.right = currentNode.left if currentNode.left is not None else currentNode.right
break
return self
def getMinValue(self):
currentNode =self
while currentNode.left is not None:
currentNode =currentNode.left
return currentNode.value
Solution Overview
Here's a breakdown of the solution.
__init__ method
The __init__() method Initializes a new instance of the BST class with a given value. By default, the left and right children of the node are set to None.
insert method
Inserts a new node with the given value into the BST while maintaining the BST property.
contains method
Searches for a given value in the BST. Returns True if the value is found in the tree, False otherwise.
remove method
The remove() method is responsible for removing a node with the given value from the BST while maintaining the BST property.
It handles various cases some of which include:
- removing a node with no children, one child, or two children.
- It ensures that the resulting tree remains a valid BST.
getMinValue method
It is a helper method for finding the minimum value in the subtree rooted at the current node. This method is called when removing a node with two children.
Time Complexity: Insertion, Searching, and Removal:
Average Case: O(log(n)) time complexity, where n is the number of nodes in the BST. This is because on average, each operation reduces the search space by half.
Worst Case: O(n) time complexity, which occurs when the tree is unbalanced, resembling a linear linked list.
Space Complexity
All methods have an average and worst-case space complexity of O(1), as they operate without requiring additional space proportional to the size of the tree.
Unit Tests
These tests cover various scenarios including:
- Insertion of a new node.
- Checking if a value is present in the BST.
- Removing a leaf node.
- Removing a node with one child.
- Removing a node with two children.
- Testing the getMinValue helper method.
import unittest
class TestBST(unittest.TestCase):
def setUp(self):
# Create a BST for testing
self.bst = BST(10)
self.bst.insert(5)
self.bst.insert(15)
self.bst.insert(2)
self.bst.insert(7)
self.bst.insert(12)
self.bst.insert(17)
def test_insert(self):
# Test insertion of a new node
self.bst.insert(20)
self.assertTrue(self.bst.contains(20))
def test_contains(self):
# Test contains method for existing and non-existing values
self.assertTrue(self.bst.contains(7))
self.assertFalse(self.bst.contains(8))
def test_remove_leaf_node(self):
# Test removal of a leaf node
self.bst.remove(2)
self.assertFalse(self.bst.contains(2))
def test_remove_node_with_one_child(self):
# Test removal of a node with one child
self.bst.remove(15)
self.assertFalse(self.bst.contains(15))
self.assertTrue(self.bst.contains(17))
def test_remove_node_with_two_children(self):
# Test removal of a node with two children
self.bst.remove(15)
self.assertFalse(self.bst.contains(15))
self.assertTrue(self.bst.contains(12))
self.assertTrue(self.bst.contains(17))
def test_get_min_value(self):
# Test getMinValue method
min_value = self.bst.getMinValue()
self.assertEqual(min_value, 2)
if __name__ == '__main__':
unittest.main()
Use Cases
The BST data structure is commonly used in applications requiring efficient searching, such as databases, binary search, and data indexing