Problem Statement
Implement BST class for a binary search tree with these features:
- Inserting values.
- Removing values, which applies to the first instances found.
- Searching for values.
Sample Input
tree = 10
/ \
1 15
/ \ / \
2 5 13 22
/ \
1 14
Sample Result
insert(12) = 10
/ \
1 15
/ \ / \
2 5 13 22
/ / \
1 12 14
remove(10) = 12
/ \
1 15
/ \ / \
2 5 13 22
/ \
1 14
Code #1
class BST:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(self, value):
# case value == int
cur_node = self
while True:
if value < cur_node.value:
if cur_node.left is not None:
cur_node = cur_node.left
else:
cur_node.left = BST(value)
return self
elif value >= cur_node.value:
if cur_node.right is not None:
cur_node = cur_node.right
else:
cur_node.right = BST(value)
return self
return self
def contains(self, value):
if self.find_node(value)[0] is not None:
return self.find_node(value)[0].value == value
else:
return False
def remove(self, value, parent_node=None):
cur_node = self
while cur_node is not None:
if value > cur_node.value:
parent_node = cur_node
cur_node = cur_node.right
elif value < cur_node.value:
parent_node = cur_node
cur_node = cur_node.left
# case there is duplicate value
elif cur_node.right is not None and value == cur_node.right.value:
parent_node = cur_node
cur_node = cur_node.right
# if cur_node is none, aka value not found, the loop will break here
else:
if parent_node is None:
if cur_node.left is not None and cur_node.right is not None:
cur_node.value = cur_node.right.get_min_value()
cur_node.right.remove(cur_node.value, cur_node)
elif cur_node.left is not None and cur_node.right is None:
cur_node.value = cur_node.left.value
cur_node.right = cur_node.left.right
cur_node.left = cur_node.left.left
break
elif cur_node.left is None and cur_node.right is not None:
cur_node.value = cur_node.right.get_min_value()
cur_node.right.remove(cur_node.value, cur_node)
elif cur_node.left is None and cur_node.right is None:
# case trying to remove root node but they have no child
break
else:
if cur_node.left is not None and cur_node.right is not None:
cur_node.value = cur_node.right.get_min_value()
cur_node.right.remove(cur_node.value, cur_node)
elif cur_node.left is not None and cur_node.right is None:
cur_node.value = cur_node.left.value
cur_node.right = cur_node.left.right
cur_node.left = cur_node.left.left
break
elif cur_node.left is None and cur_node.right is not None:
cur_node.value = cur_node.right.get_min_value()
cur_node.right.remove(cur_node.value, cur_node)
elif cur_node.left is None and cur_node.right is None:
# case removing leaf node
if parent_node.left == cur_node:
parent_node.left = None
elif parent_node.right == cur_node:
parent_node.right = None
break
return self
def find_node(self, value):
cur_node = self
parent_node = cur_node
while True:
if value == cur_node.value:
return cur_node, parent_node
elif cur_node.left is None and cur_node.right is None:
return None, None
elif value < cur_node.value:
if cur_node.left is not None:
parent_node = cur_node
cur_node = cur_node.left
else:
return None, None
elif value >= cur_node.value:
if cur_node.right is not None:
parent_node = cur_node
cur_node = cur_node.right
else:
return None, None
def get_min_value(self):
cur_node = self
while cur_node.left is not None:
cur_node = cur_node.left
return cur_node.value
Notes
- Using interative approach yields better space complexity, although somewhat harder to implement and not intuitive as the recursive approach.
Credits
- Algoexpert for the problem statement.
- Tomas Robertson for the cover image (https://unsplash.com/photos/wAKld_0lcmA).
Top comments (0)