I'm trying to remove make a function that deletes any element of the BST. Everything works well except the case when I try to delete the root of the tree (by the root I mean the first element of the list when printing tree pre-order). When I try to delete that element, nothing gets deleted. I'm not sure what causes this issue.
class Node:
def __init__(self, value=None):
self.value = value
self.left = None
self.right = None
def insert(self, value):
if not self.value:
self.value = value
return
if value < self.value:
if self.left:
self.left.insert(value)
return
self.left = Node(value)
return
if value > self.value:
if self.right:
self.right.insert(value)
return
self.right = Node(value)
def pre_order(self, values):
if self.value is not None:
values.append(self.value)
if self.left is not None:
self.left.pre_order(values)
if self.right is not None:
self.right.pre_order(values)
return values
def delete(self, value):
if self == None:
return self
if value < self.value:
self.left = self.left.delete(value)
return self
if value > self.value:
self.right = self.right.delete(value)
return self
if self.right == None:
return self.left
if self.left == None:
return self.right
min_larger_node = self.right
while min_larger_node.left:
min_larger_node = min_larger_node.left
self.value = min_larger_node.val
self.right = self.right.delete(min_larger_node.value)
return self
l = [1, 2, 3, 4, 5, 6]
BST = Node()
for i in l:
BST.insert(i)
before_deleting = []
print(BST.pre_order(before_deleting))
BST.delete(1)
after_deleting = []
print(BST.pre_order(after_deleting))
except the case when I try to delete the root of the tree
This is because the root node is represented by your BST variable, and nothing gets assigned to that variable when you call delete.
There are more problems though:
If you call the delete method with a value that is not found in the tree, an exception will occur, because a call to self.left.delete(value) will be made at a moment that self.left is None. You can avoid this by calling the method as if it were a static method: Node.delete(self.left, value).
When you call delete on a node that has two children, an error occurs on self.value = min_larger_node.val. There is no val attribute. It should be value.
If the value 0 is added to the tree with insert(0), it might get overwritten. For instance, if the input is [2, 0, 1], the tree will end up with only 2 and 1. This is because of a peculiar handling with a not self.value condition (see below).
Even if you assign the result of BST.delete() back to the BST name, you'll eventually get an empty tree where BST is None, and then calling any method on BST (like BST.pre_order()) will fail with an error.
With the initialisation of the tree you have worked around the previous issue by adding a dummy node with value None, which is also the reason why you have this not self.value condition in your code -- but it breaks the correct functioning of your tree. You should not have such dummy node, but regard an empty tree as a tree without nodes, not with a dummy node. Instead, create a second class that will deal with the None value you might have for the root.
Not a major problem, but it is not nice that one has to pass a list as argument to pre_order. It would be better if that method would create the list itself and return it. It is also more pythonic to use a generator for producing the values according to a pre order traversal.
Here is how that would work:
class Node:
def __init__(self, value): # No special None value (removed default)
self.value = value
self.left = None
self.right = None
def insert(self, value):
# No special condition for detecting dummy nodes here.
if not self:
return Node(value)
if value < self.value:
self.left = Node.insert(self.left, value)
elif value > self.value:
self.right = Node.insert(self.right, value)
return self
def delete(self, value):
if not self:
return self
if value < self.value:
self.left = Node.delete(self.left, value) # Safe for when None
return self
if value > self.value:
self.right = Node.delete(self.right, value)
return self
if not self.right:
return self.left
if not self.left:
return self.right
min_larger_node = self.right
while min_larger_node.left:
min_larger_node = min_larger_node.left
self.value = min_larger_node.value
self.right = self.right.delete(min_larger_node.value)
return self
def pre_order(self): # generator
if self:
yield from Node.pre_order(self.left)
yield from Node.pre_order(self.right)
yield self.value
class BST: # Container class for managing the root
def __init__(self):
self.root = None # An empty tree has no nodes: no dummies!
def insert(self, value):
self.root = Node.insert(self.root, value)
def delete(self, value):
self.root = Node.delete(self.root, value)
def pre_order(self): # generator
return Node.pre_order(self.root)
lst = [4, 2, 6, 1, 3, 5, 7]
tree = BST()
for value in lst:
tree.insert(value)
tree.delete(4)
print(*tree.pre_order()) # 1 3 2 7 6 5