# FAQ: Binary Search Trees: Python - Review

This community-built FAQ covers the “Review” exercise from the lesson “Binary Search Trees: Python”.

Paths and Courses
This exercise can be found in the following Codecademy content:

## FAQs on the exercise Review

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.

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!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

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.

1 Like

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
``````

Please let me know if this works for y’all!

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:
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:
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:
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()
``````