delete function for binary search tree not working in python

Question

class Node:
    def __init__(self,value = None):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self,value):
        if self.root != None:
            self._insert(self.root,value)
        else:
            self.root = Node(value)

    def _insert(self,current,value):
        if value < current.value:
            if current.left == None:
                current.left = Node(value)
            else:
                self._insert(current.left,value)

        elif value > current.value: 
            if current.right == None:
                current.right = Node(value)
            else:   
                self._insert(current.right,value)
        else:
            print("Value already exist in tree.")


    def delete(self,current,value):
        if current == None: return current
        elif value < current.value: current.left = self.delete(current.left,value)
        elif value > current.value: current.right = self.delete(current.right,value)
        else:
            if current.left == None and current.right == None:
                current = None # case 0
            elif current.left == None: return current.right # case 1r
            elif current.right == None: return current.left # case 1l
            else:  # case 2
                temp = self.min(current.right)
                current.value = temp
                self.delete(current.right,temp)
        return current

    def min(self,current): 
        if current != None:
            return self._min(current)
        else:
            return None

    def _min(self,current):
        if current.left != None:
            return self._min(current.left)
        else:
            return current.value

if __name__ == '__main__':
    for i in (12,5,18,3,4,6):
        tree.insert(i)
    tree.delete(tree.root,12)

Hi guys, my binary search tree's delete function is not working for nodes with 2 children and would appreciate some help here.

The problem is caused by line 6 and 12 of the delete function, where the line self.delete(current.right,temp) leads to current = None # case 0. The line current = None # case 0 doesn't change the value of current to 0, which I am very confused about. Any idea what's wrong?

That will only set the local current to None, not the value that you passed into the function. I assume that's what you expected? — Jeronimo
– Jeronimo, Commented Dec 11, 2017 at 8:22

lty · Accepted Answer · 2017-12-11 08:34:13Z

2

Replace line 12 in delete method with:

current.right = self.delete(current.right, temp)

The reason is simple: current=None only affect a local value, it cannot affect node 12's left child or right child.

answered Dec 11, 2017 at 8:34

lty

1282 silver badges7 bronze badges

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

Collectives™ on Stack Overflow

delete function for binary search tree not working in python

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related