There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
You can also find further discussion and get answers to your questions over in Language Help.
Agree with a comment or answer? Like () to up-vote the contribution!
Since there is no solution posted for the delete function yet I want to post my iterative solution.
I did this solution with a parent reference inside the TreeNode Class. I tried to solve it recursively without this reference, but I just couldnt get my head around it.
This is the delete function:
def delete(self, value):
current = self
while True:
if current.value > value:
if current.left is not None:
current = current.left
continue
else:
print("no such node")
break
if current.value < value:
if current.right is not None:
current = current.right
continue
else:
print("no such node")
break
if current.value == value:
print("node to delete found")
break
# no child case
if (current.left is None) and (current.right is None):
if current.parent.value > current.value:
current.parent.left = None
return None
else:
current.parent.right = None
return None
# 1 child case
if current.left is None:
current.value = current.right.value
insertion_list = current.right.collect_all_children_to_list()
current.right = None
for node in insertion_list:
self.insert(node.value)
return
if current.right is None:
current.value = current.left.value
insertion_list = current.left.collect_all_children_to_list()
for node in insertion_list:
self.insert(node.value)
current.left = None
return
# 2 child case
min_node_in_right_child = getMinValueNode(current.right)
current.delete(min_node_in_right_child.value)
current.value = min_node_in_right_child.value
return
These are the helper functions:
def getMinValueNode(node):
current = node
# loop down to find the leftmost leaf
while (current.left is not None):
current = current.left
return current
def collect_all_children_to_list(self, list=None):
if list is None:
list = []
if (self.left is None) and (self.right is None):
return list
if self.left is not None:
list.append(self.left)
self.left.collect_all_children_to_list(list)
if self.right is not None:
list.append(self.right)
self.right.collect_all_children_to_list(list)
return list
This is the customized init and insert method:
def __init__(self, value, depth=1, parent=None):
self.value = value
self.depth = depth
self.left = None
self.right = None
self.parent = parent
def insert(self, value):
if (value < self.value):
if (self.left is None):
self.left = BinarySearchTree(value, self.depth + 1, self)
print(f'Tree node {value} added to the left of {self.value} at depth {self.depth + 1}')
else:
self.left.insert(value)
else:
if (self.right is None):
self.right = BinarySearchTree(value, self.depth + 1, self)
print(f'Tree node {value} added to the right of {self.value} at depth {self.depth + 1}')
else:
self.right.insert(value)
Feedback or criticism is appreciated, because I dont think this is the best solution.
I like this. It is involved but as I am new to this I don’t see a way to streamline it. It seems like you need all the cases.
I saw the problem very differently. I modified the depth_first_traversal function to return a list of the values. I deleted the node value from this list. Then I made a new tree with the remaining node values.
This was my solution for deleting via depth first traversal. It uses recursion through the depth first traversal method that we learned through the modules, and basically two methods, tree rotation and left tree shift:
def remove_dft(self, value) -> bool:
if self.value == value:
if self.right:
# Move right node up to be the parent, then do tree rotation
self.right_rotation()
elif self.left:
# Move left node up to be the parent
self.left_shift()
else:
# No children, this node needs to be dereferenced
self.value = None
return True
if self.left:
found = self.left.remove_dft(value)
if found:
# Dereference empty node
if self.left.value == None:
self.left = None
return True
if self.right:
found = self.right.remove_dft(value)
if found:
# Dereference empty node
if self.right.value == None:
self.right = None
return True
return False
def left_shift(self):
if self.left:
# Shift left node to be the parent
self.value = self.left.value
self.right = self.left.right
self.left = self.left.left
return True
return False
def right_rotation(self):
if self.right:
# Rotate right node up
self.value = self.right.value
self.right = self.right.right
# Move orphaned left node into the leftmost node of the new parent
orphaned_left_node = self.left
if orphaned_left_node and self.right and self.right.left:
leftmost_node = self.right.left
while leftmost_node.left:
leftmost_node = leftmost_node.left
leftmost_node.left = orphaned_left_node
else:
self.left = orphaned_left_node
return True
return False
Hello, my fellow coders. Here are my delete and balance features for the binary search tree in this lesson. I had to create several other methods for these to work, (.parent, .most_left, .most_right, .is_leaf). Here I distinguish between deleting leaves and not leaves from the tree, that’s why I created the .parent and .is_leaf methods, since when a leaf is removed it is not replaced with any other value; the .most_left and .most_right methods are for correctly replacing the deleted nodes. I also created private helper methods for the .get_node_list and .balance methods because I had trouble keeping the same list from call to call in the recursion. Please try it and let me know if it works for you.
class BinarySearchTree:
def __init__(self, value, depth=1):
self. Value = value
self.depth = depth
self.left = None
self.right = None
def insert(self, value):
if (value < self.value):
if (self.left is None):
self.left = BinarySearchTree(value, self.depth + 1)
#print(f'Tree node {value} added to the left of {self.value} at depth {self.depth + 1}')
else:
self.left.insert(value)
else:
if (self.right is None):
self.right = BinarySearchTree(value, self.depth + 1)
#print(f'Tree node {value} added to the right of {self.value} at depth {self.depth + 1}')
else:
self.right.insert(value)
def get_node_by_value(self, value):
if (self.value == value):
return self
elif ((self.left is not None) and (value < self.value)):
return self.left.get_node_by_value(value)
elif ((self.right is not None) and (value >= self.value)):
return self.right.get_node_by_value(value)
else:
return None
def depth_first_traversal(self):
if (self.left is not None):
self.left.depth_first_traversal()
print(f'Depth={self.depth}, Value={self.value}')
if (self.right is not None):
self.right.depth_first_traversal()
def most_left(self):
if not self.left:
return self
else:
return self.left.most_left()
def most_right(self):
if not self.right:
return self
else:
return self.right.most_right()
def parent(self, value, depth):
if self.value <= value and self.right:
if self.right.value == value and self.right.depth == depth:
return self
else:
return self.right.parent(value, depth)
if self.value > value and self.left:
if self.left.value == value and self.left.depth == depth:
return self
else:
return self.left.parent(value, depth)
return
def is_leaf(self):
return not self.left and not self.right
def delete(self, value, depth):
if depth < 1:
raise ValueError("Depth must be positive")
elif self.value <= value and self.depth < depth:
if self.right:
if self.right.is_leaf() and self.right.value == value and self.right.depth == depth:
self.right = None
else:
return self.right.delete(value, depth)
else:
raise ValueError(f"Value {value} at depth {depth} not found in tree")
elif self.value > value:
if self.left:
if self.left.is_leaf() and self.left.value == value and self.left.depth == depth:
self.left = None
else:
return self.left.delete(value, depth)
else:
raise ValueError(f"Value {value} at depth {depth} not found in tree")
elif self.value == value and self.depth == depth:
if self.right:
rml = self.right.most_left()
parent = self.parent(rml.value, rml.depth)
if self.value == parent.value and self.depth == parent.depth:
self.right = rml.right
else:
parent.left = rml.right
self.value = rml.value
elif self.left:
lmr = self.left.most_right()
parent = self.parent(lmr.value, lmr.depth)
if self.value == parent.value and self.depth == parent.depth:
self.left = lmr.left
else:
parent.right = lmr.left
self.value = lmr.value
else:
raise ValueError("Cannot delete one node tree")
else:
raise ValueError(f"Value {value} at depth {depth} not found in tree")
return
def __get_node_list(self, node_list):
if self.left:
self.left.__get_node_list(node_list)
node_list.append(self.value)
if self.right:
self.right.__get_node_list(node_list)
return node_list
def get_node_list(self):
return self.__get_node_list([])
def __balance(self, nlst):
self.value = nlst[len(nlst)//2]
left = nlst[:len(nlst)//2]
right = nlst[len(nlst)//2 + 1:]
if left:
self.left = BinarySearchTree(left[len(left)//2], self.depth + 1)
self.left.__balance(left)
if right:
self.right = BinarySearchTree(right[len(right)//2], self.depth + 1)
self.right.__balance(right)
def balance(self):
self.__balance(self.get_node_list())
print("Creating Binary Search Tree rooted at value 15:")
tree = BinarySearchTree(15)
tree.insert(13)
tree.insert(15)
tree.insert(29)
tree.insert(45)
tree.insert(49)
tree.insert(55)
tree.insert(58)
tree.insert(63)
tree.insert(77)
tree.insert(82)
tree.insert(86)
tree.depth_first_traversal()
print("Deleting node with value 58 at depth 7...")
tree.delete(58, 7)
tree.depth_first_traversal()
print("Balancing tree..")
tree.balance()
tree.depth_first_traversal()
) below.
) to up-vote the contribution!