Binary Search Tree Python, Implementing Delete

Question

I am trying to implement a binary search tree in python, but I can't find a solution for delete. If the item is in a leaf, that is simple, but what if the item I want to delete has 2 children which also have other children and so on ? How can in find its successor, so that I can replace it ? Are there any simple recursive solutions ?

class Node:

    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right    


class BinarySearchTree:


    def __init__(self, root=None):
        self.root = Node(root)


    def add(self, data, node):

        if node == None:
            node = Node(data)
            return True

        if data < node.data:
            if node.left == None:
                node.left = Node(data)
                return True
            else:
                self.add(data, node.left)
        elif data > node.data:
            if node.right == None:
                node.right = Node(data)
                return True
            else:
                self.add(data, node.right)


    def preorder(self, node):
        if node != None:
            print(node.data)
            self.preorder(node.left)
            self.preorder(node.right)

    def inorder(self, node):
        if node != None:
            self.inorder(node.left)
            print(node.data)
            self.inorder(node.right)

    def postorder(self, node):
        if node != None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data)


    def retreive(self,item):

        node = self.root

        while node != None:
            if node.data == item:
                break
            elif item < node.data:
                if node.left != None:
                    if node.left.data == item:
                        node.left = None
                        return True
                node = node.left
            else:
                if node.right != None:
                    if node.right.data == item:
                        node.right= None
                        return True
                node = node.right

        if node == None:                
            return False

tree = BinarySearchTree()
root=Node(3)
tree.add(55,root)
tree.add(5,root)
tree.add(13,root)
tree.add(2,root)
tree.add(3,root)
tree.preorder(root)
tree.postorder(root)
tree.inorder(root)

Also if you have any suggestions for what I've written so far, I'd really appreciate it. Thanks in advance.

The Wikipedia article has a pretty good explanation of the approach to use here. — Andrew Clark
– Andrew Clark, Commented Nov 22, 2013 at 23:16

dstromberg · Accepted Answer · 2013-11-22 23:51:08Z

3

If this isn't homework, you might use one of these:

Both implement deletion. Both deal well with sorted or unsorted inputs.

The red-black tree module has a BinaryTree class that RedBlackTree inherits from.

answered Nov 22, 2013 at 23:51

dstromberg

7,2432 gold badges31 silver badges30 bronze badges

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

Collectives™ on Stack Overflow

Binary Search Tree Python, Implementing Delete

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related