data structures - PYTHON Binary Search Tree - Recursive Remove -

i'm working on binary search tree class , have implement remove method using recursion. here code given us.

def remove (self, x):     def recurse (p):         # modify method.         if p==none:             return p         elif x<p.data:             return p         elif x>p.data:             return p         elif p.left==none , 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 more return p each conditional. , i'm pretty sure first if , 2 elifs used 'locate' node containing x. not sure how implement 4 cases. input appreciated.

also, end goal use method iterate through bst , remove each node.

well, first step locate x, remember recursion, should recurse remove function on child tree located. (left if x < p.data, right if higher... if exist). next, need worry once find x (x = p.data).

i recommend drawing tree , think algorithm. :)

remember bst property! tree necesarily modify it's structure preserve property, so.. new father of lonely childs? hints:

sibling possibly?

.

remember bst charasteristic

.

recursion!!!)