Binary Search Tree
Initiate the class
class BST:
def __init__(self,value):
self.value = value
self.left = None
self.right = None
Insert a value into the tree
# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space - In case of a tree with single branch
def insert(self,value):
= self
currentNode while True:
if value < currentNode.value:
# If the value to be inserted is less then the current node's value
# and the left node is None, then insert the value there
# If the left node is not none, the current node is the left node
if currentNode.left is None:
= BST(value)
currentNode.left break
else:
= currentNode.left
currentNode
else:
# This is when the value to be inserted is greater than the current node's value
if currentNode.right is None:
= BST(value)
currentNode.right break
else:
= currentNode.right
currentNode return self
Search for a value in the tree
# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space
def contains(self,value):
= self
currentNode while currentNode is not None:
if value < currentNode.value:
= currentNode.left
currentNode elif value > currentNode.value:
= currentNode.right
currentNode else:
return True
return False
Remove a value from the tree
# Average O(log(n)) time | O(1) space
# Worst O(n) time | O(1) space
def remove(self,value):
= self
currentNode while currentNode is not None:
if value < currentNode.value:
= currentNode
parentNode = currentNode.left
currentNode elif value > currentNode.value:
= currentNode
parentNode = currentNode.right
currentNode else:
# When value is equal to currentNode.value
if currentNode.left is not None and currentNode.right is not None:
# when both left and right nodes are not None
# find the node with the minimum value in the right subtree
# and replace the value of the node with the minimum value
# remove the minimum value from the right subtree
= currentNode.right.getMinValue()
currentNode.value
currentNode.right.remove(currentNode.value, currentNode)elif parentNode is None:
# When currentNode is the root node
if currentNode.left is not None:
= currentNode.left.value
currentNode.value = currentNode.left.right
currentNode.right = currentNode.left.left
currentNode.left elif currentNode.right is not None:
= currentNode.right.value
currentNode.value = currentNode.right.left
currentNode.left = currentNode.right.right
currentNode.right else:
= None
currentNode.value elif parentNode.left = currentNode:
= currentNode.left if currentNode.left is not None else currentNode.right
parentNode.left elif parentNode.right = currentNode:
= currentNode.left if currentNode.left is not None else currentNode.right
parentNode.right break
return self
def getMinValue(self):
= self
currentNode while currentNode.left is not None:
= currentNode.left
currentNode return currentNode.value