PYTHON Binary Search Tree - Recursive Remove

Question

I'm working on a binary search tree class and we have to implement the remove method using recursion. Here is the code that was given to us.

def remove (self, x):
 def recurse (p):
 # Modify this method.
 if p==None:
 return p
 elif x<p.data:
 return p
 elif x>p.data:
 return p
 elif p.left==None and p.right==None: # case (1)
 return p
 elif p.right==None: # case (2)
 return p
 elif p.left==None: # case (3)
 return p
 else: # case (4) 
 return p
 self.root = recurse (self.root)

Obviously there should be more than just return p for each conditional. And I'm pretty sure the first if and two elifs are used to 'locate' the node containing x. However I am not sure how to implement the four cases. Any input would be appreciated.

Also, the end goal is to use this method to iterate through the BST and remove each node.

• Joran Beasley: what is one requirement of recursion? it needs to _______, and must have at least one ___________.

Answer 1

Well, your first step is to locate X, remember that you do this by recursion, so you should recurse the remove function on the child tree its located. (left if x < p.data, right if higher... only if they exist). Next, you need to worry what to do once you find x (x = p.data).

I would recommend drawing a tree and think as an algorithm. :)

Remember the BST property! The tree will necesarily modify it's structure to preserve the property, so.. who is the new father of the lonely childs? hints:

a sibling possibly?

.

remember the BST charasteristic

.

recursion!!!)

• Joran Beasley: reasonable answer ... good job not acutally spoiling the assignment
• John Ruddell: agreed, the OP needs to figure it out on his own without just getting the answer... but getting pointers as to how to tackle it is helpful
• johnsmith101: Thanks, that helps a lot. When you say "recurse the remove function", would you actually be returning the recurse? For example if x < p.data, I should return recurse(p.right)?
• LucasP: yep, you have to return the final value through the recursion tree.

Answer 2

pseudo_code method_recurse requires argument: this_node

1. if this_node is None then return None Found
2. if this_node is target then return this_node
3. if this_node is less_than target then return call self with this_node.right
4. if this_node is greater_than target then return call self with this_node.left