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.

what is one requirement of recursion? it needs to _______, and must have at least one ___________. — Joran Beasley
– Joran Beasley, Commented Apr 9, 2015 at 23:12

LucasP · Accepted Answer · 2015-04-09 23:17:51Z

2

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!!!)

edited Apr 9, 2015 at 23:17

answered Apr 9, 2015 at 23:11

LucasP

3133 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Joran Beasley Over a year ago

reasonable answer ... good job not acutally spoiling the assignment

John Ruddell Over a year ago

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 Over a year ago

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 Over a year ago

yep, you have to return the final value through the recursion tree.

Joran Beasley · Accepted Answer · 2015-04-09 23:18:39Z

1

pseudo_code method_recurse requires argument: this_node

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

answered Apr 9, 2015 at 23:18

Joran Beasley

114k13 gold badges167 silver badges187 bronze badges

Collectives™ on Stack Overflow

PYTHON Binary Search Tree - Recursive Remove

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related