Deleting nodes from a tree in Python

Question

Below is a program I am working on that creates a tree and then can delete nodes from the tree. Im having trouble understanding just how deleting a node works and am looking for a bit of guidance. Currently My code replaces the node with the left most leaf, but Im trying to get it to delete the whole thing like it was never there. This is the area I am running into confusion with. Can someone explain?

 def remove(self, data):
 if self.root and self.root.data == data: # special case for removing the root
 self.root = self.root.delete()
 return
 else: # general case, removing a child node of some parent
 parent = self.root
 while parent:
 if data < parent.data:
 child = parent.left
 if child and child.data == data:
 if child.left == None and child.right == None:
 parent.left = None
 return
 if child.left == None:
 parent.left = child.right
 child = None
 return
 if child.right == None:
 parent.left = child.left
 child = None
 return
 left_most = child
 while left_most.left != None:
 second_left = left_most
 left_most = left_most.left
 child.data = left_most.data
 second_left = None
 return
 parent = child
 else:
 child = parent.right
 if child and child.data == data:
 if child.left == None and child.right == None:
 parent.right = None
 return
 if child.left == None:
 parent.right = child.right
 child = None
 return
 if child.right == None:
 parent.right = child.left
 child = None
 return
 left_most = child
 while left_most.left != None:
 second_left = left_most
 left_most = left_most.left
 child.data = left_most.data
 second_left = None
 return
 parent = child

• JacobIRR: Could you provide some sample input and show us the comparison between the actual output you get and the expected output you want?
• Menachem Hornbacher: What type of tree is this? AVR Binary Search? min_heap? max_heap?
• alienmode: I added a sample input and output. Hopefully it explains it a little better.
• Blckknght: What do you expect the 11 to be replaced by? Do you want it to delete the whole subtree rooted there (so that 21 would have no nodes on the left)? Or do you expect it to preserve the order of the elements (in which case you need 11's right sub-tree's leftmost value or the left sub-tree's rightmost value.
• alienmode: I am looking for a way to make it remake the whole tree without the deleted node, so it would be preserving all the other input numbers like the deleted one was never there.

Answer 1

The homework assignment this question comes from links to a webpage that shows how the deletion is to be performed. Maybe you should post the entire assignment so that you can get your question answered.