Cannot Delete the root node in a Binary search Tree

Question

I have recently started learning and Implementing some data structures in Python and was trying Binary Search tree and completed the code. Everything is running fine except the deletion of root node. I have divided my code into 3 modules

Here is my Code :

Node.py

class Node:

def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild = None


def insert(self, data):
    if data < self.data:
        if not self.leftChild:
            self.leftChild = Node(data)
        else:
            self.leftChild.insert(data)
    else:
        if not self.rightChild:
            self.rightChild = Node(data)
        else:
            self.rightChild.insert(data)


def remove(self, data, parentNode): 
    if data < self.data:
        if self.leftChild is not None:
            self.leftChild.remove(data, self)

    elif data > self.data:
        if self.rightChild is not None:
            self.rightChild.remove(data, self)

    else:
        if self.leftChild is not None and self.rightChild is not None:
            self.data = self.rightChild.getMin()
            self.rightChild.remove(self.data, self)

        elif parentNode.leftChild == self:
            if self.leftChild is not None:
                tempNode = self.leftChild
            else:
                tempNode = self.rightChild



            parentNode.leftChild = tempNode


        elif parentNode.rightChild == self:
            if self.leftChild is not None:
                tempNode = self.leftChild
            else:
                tempNode = self.rightChild

            parentNode.rightChild = tempNode


def getMin(self):
    if self.leftChild is None:
        return self.data
    else:
        self.leftChild.getMin()


def getMax(self):
    if self.rightChild is None:
        return self.data
    else:
        self.rightChild.getMax()


def traverseInOrder(self):
    if self.leftChild is not None:
        self.leftChild.traverseInOrder()    
    print(self.data)

    if self.rightChild is not None:
        self.rightChild.traverseInOrder()

BinarySearchTree.py

from BinarySearchTrees.Node import Node


class BST:

def __init__(self):
    self.rootNode = None;


def insert(self, data):
    if self.rootNode is None:
        self.rootNode = Node(data)

    else:
        self.rootNode.insert(data)


def removal(self, dataToRemove):
    if self.rootNode:
        if self.rootNode.data == dataToRemove:
            tempNode = Node(None)
            tempNode.leftChild = self.rootNode
            print("The value of dataToRemove : " + str(dataToRemove))
            self.rootNode.remove(dataToRemove, tempNode)
        else:
            self.rootNode.remove(dataToRemove, None)


def getMin(self):
    if self.rootNode:
        return self.rootNode.getMin()

def getMax(self):
    if self.rootNode:
        return self.rootNode.getMax()

def traverseInOrder(self):
    if self.rootNode:
        self.rootNode.traverseInOrder()

Output.py

from BinarySearchTrees.BinarySearchTree import BST

bst = BST()

bst.insert(5)
bst.insert(8)
bst.insert(3)
bst.insert(7)

bst.insert(9)
bst.insert(4)
bst.insert(2)



bst.traverseInOrder()
bst.removal(5)
bst.traverseInOrder()

and the Error with the Removal command is :

    Traceback (most recent call last):
  File "G:\Docs\Liclipse Projects\DS\BinarySearchTrees\Output.py", line 16, in <module>
    bst.removal(5)
  File "G:\Docs\Liclipse Projects\DS\BinarySearchTrees\BinarySearchTree.py", line 24, in removal
    self.rootNode.remove(dataToRemove, tempNode)
  File "G:\Docs\Liclipse Projects\DS\BinarySearchTrees\Node.py", line 34, in remove
    self.rightChild.remove(self.data, self)
  File "G:\Docs\Liclipse Projects\DS\BinarySearchTrees\Node.py", line 23, in remove
    if data < self.data:
TypeError: '<' not supported between instances of 'NoneType' and 'int'

It's like the data parameter passed in remove function in Node is returning a None value despite of giving a value in the BinarySearchTree removal function.

If anyone could find the error in my code please tell me the solution. It would be a great help..

I don't have a fully baked answer for your specific issue, but a general suggestion that should make things a lot easier: Rather than passing the parent node into Node.remove, have it return a Node instead. The return value could either be self, one of the child nodes, or None if a leaf node is being deleted. This allows the nodes to not care which child they are of their parent. Since it's the parent that's making the call, it already knows which child it's calling the method on. Use something like self.leftChild = self.leftChild.remove(some_value) for the recursion. — Blckknght
– Blckknght, Commented Feb 9, 2018 at 21:09

JacobIRR · Accepted Answer · 2018-02-09 20:31:09Z

1

Both instances of if data < self.data: should be : if data is not None and (data < self.data):

This will short circuit the check when data is not None

answered Feb 9, 2018 at 20:31

JacobIRR

9,0468 gold badges46 silver badges73 bronze badges

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

Collectives™ on Stack Overflow

Cannot Delete the root node in a Binary search Tree

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related