Search code examples
pythonbinary-search-tree

Binary Search Tree inorder not working (python)


I've been messing around learning about objects and classes, and as I finally felt that I managed to wrap my head around how to construct a Binary Search Tree in python, I ran into an issue. Here's my code:

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

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

    def add(self,current,value):
        if self.root == None:
            self.root = node(value)
        else:
            if value < current.value:
                if current.left == None:
                    current.left = node(value)
                else:
                    self.add(current.left,value)
            if value > current.value:
                if current.right == None:
                    current.right = node(value)
                else:
                    self.add(current.right,value)

    def visit(self,node):
        print(node.value)

    def inorder(self,current):
        self.inorder(current.left)
        self.visit(current)
        self.inorder(current.right)

Tree = BST()
root = node(2)
Tree.root = root
Tree.add(Tree.root,7)

Tree.inorder(Tree.root)

after running the code, I got an error: AttributeError: 'NoneType' object has no attribute 'left'. The error comes out of the inorder function, as apparently the value I'm inserting into the function is an object without a type. as you can see, the root of the tree is a node object, so it should have the attribute "left" as per coded in the class. I would really appreciate if someone could help me with what I'm getting wrong. Thanks in advance!

EDIT: I should note that I checked whether the root is a node with the isinstance(), function, and indeed it returned True.


Solution

  • I think you sould check current is not None before access its left and right.

      def inorder(self, current):
            if current:
                self.inorder(current.left)
                self.visit(current)
                self.inorder(current.right)