def _find_smallest_and_parent(self, start_node):
""" (BST) -> (BinTreeNode, BinTreeNode)
Return a node with the smallest value
in the sub-tree rooted at start_node, plus its parent.
REQ: start_node != None
"""
# finding smallest is same as finding left most
curr = start_node
parent = None
while curr.left != None:
parent = curr
curr = curr.left
return (curr, parent)
def delete(self, value):
""" (BST, str) -> NoneType
Delete a node whose data is value
from this BST.
The BST is unchanged if it does not
contain a node whose data is value.
"""
(del_node, del_parent) = self._find(value)
# if there is a node to delete
if del_node != None:
# if node to delete has no left child
if del_node.left == None:
# if node to delete is root
if del_parent == None:
self._root = del_node.right
# elif node to delete is a left child
elif del_parent.left == del_node:
del_parent.left = del_node.right
# else node to delete must be a right child
else:
del_parent.right = del_node.right
# elif node to delete has no right child
elif del_node.right == None:
# if node to delete is root
if del_parent == None:
self._root = del_node.left
# elif node to delete is a left child
elif del_parent.left == del_node:
del_parent.left = del_node.left
# else node to delete must be a right child
else:
del_parent.right = del_node.left
# else node to delete has both left and right children
else:
# find node with next bigger value
(next_bigger, next_parent) = self._find_smallest_and_parent(del_node.right)
# copy data from next bigger node to node to delete
del_node.data = next_bigger.data
# delete next bigger node
# if next biggest node is right child of node to delete
if next_parent == None:
del_node.right = next_bigger.right
else:
next_parent.left = next_bigger.right