CODEWITHSUNDEEP
python
A. Radek Martinez
A. Radek Martinez

Reputation: 235

BST Tree Error: TypeError: '<=' not supported between instances of 'int' and 'Node'

I am trying to implement a BST. My code in Python is as follows: 

class Node: 
    def __init__(self, val):
        self.val = val
        self.leftChild = None
        self.rightChild = None

    def get(self):
        return self.val

    def getleftChild(self):
        return self.leftChild

    def getrightChild(self):
        return self.rightChild

    def set(self, val):
        self.val = val

    def getChildren(self):
        children = []
        if self.leftChild != None:
            children.append(self.leftChild)
        if self.rightChild != None:
            children.append(self.rightChild)
        return children

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

    def setRoot(self, val):
        self.root = Node(val)

    def insert(self, val):
        if self.root == None:
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, CurrentNode, val):
        if val <= CurrentNode.get(): 
            if CurrentNode.leftChild:
                self.insertNode(CurrentNode.leftChild, val)
            else:
                CurrentNode.leftChild = Node(val)
        elif val < CurrentNode.get():
            if CurrentNode.rightChild:
                self.insertNode(CurrentNode.rightChild, val)
            else:
                CurrentNode.rightChild = Node(val)

new_BST = BST()

root_node = Node(2)
new_BST.setRoot(root_node)

array = [4,5,2,1,6,3]

for element in array:
    new_BST.insert(element)

I keep on getting an TypeError: '<=' not supported between instances of 'int' and 'Node' on line 41 in the insertNode section and I am not sure why. I am calling .get() which is suppose to return an int, so I am not sure why the comparison will not work.

Upvotes: 0

Views: 2157

Answers (1)

Samwise
Samwise

Reputation: 71454

Type annotations make it much easier to find bugs like this:

from typing import List, Optional


class Node:
    def __init__(self, val: int):
        self.val = val
        self.leftChild: Optional['Node'] = None
        self.rightChild: Optional['Node'] = None

    def get(self) -> int:
        return self.val

    def getleftChild(self) -> Optional['Node']:
        return self.leftChild

    def getrightChild(self) -> Optional['Node']:
        return self.rightChild

    def set(self, val: int) -> None:
        self.val = val

    def getChildren(self) -> List['Node']:
        children: List['Node'] = []
        if self.leftChild is not None:
            children.append(self.leftChild)
        if self.rightChild is not None:
            children.append(self.rightChild)
        return children


class BST:
    def __init__(self):
        self.root: Optional[Node] = None

    def setRoot(self, val: int) -> None:
        self.root = Node(val)

    def insert(self, val: int) -> None:
        if self.root is None:
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, CurrentNode: Node, val: int) -> None:
        if val <= CurrentNode.get():
            if CurrentNode.leftChild:
                self.insertNode(CurrentNode.leftChild, val)
            else:
                CurrentNode.leftChild = Node(val)
        elif val < CurrentNode.get():
            if CurrentNode.rightChild:
                self.insertNode(CurrentNode.rightChild, val)
            else:
                CurrentNode.rightChild = Node(val)


new_BST = BST()

root_node = Node(2)
new_BST.setRoot(root_node)

array = [4, 5, 2, 1, 6, 3]

for element in array:
    new_BST.insert(element)

When your code is annotated, you can use static type checkers like mypy, which shows an error here:

tree.py:57: error: Argument 1 to "setRoot" of "BST" has incompatible type "Node"; expected "int"

which indeed does seem to be the problem -- you're creating a Node whose val is a Node instead of an int.

You don't see the bug until later when insertNode tries to compare the two values, which might make it hard to debug at runtime. If you declare up front that setRoot takes an int argument, though, then mypy will let you know about the mistake (and exactly where it is) even before you actually run the code.

More info on mypy and type checking here: https://mypy.readthedocs.io/en/stable/

Upvotes: 2

Related Questions