Error in Python when implementing binary search tree

Question

I am trying to implement a binary search tree using Python:

Here is my tree_node class:

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

and here is my binary tree class:

class binary_tree:
    def __init__(self,baseNode):
        self.baseNode = baseNode
    
    def addTreeNode(self,treeNode):
       current = self.baseNode
       while current:
             prev = current
             if treeNode.val < current.val:
                 current = current.rightChild
                 if prev.val < treeNode.val < current.val:
                     prev.rightChild = treeNode
                     treeNode.rightChild = current
                     break
             if treeNode.val > current.val:
                 current = current.leftChild
                 if prev.val<treeNode.val<current.val:
                     prev.leftChild = treeNode
                     treeNode.rightChild = current
       if treeNode.val<current.val:
             current.rightChild = treeNode
       elif treeNode.val>current.val:
             current.leftChild = treeNode
    
    def print_tree(self):
        currentL = self.baseNode
        currentR = self.baseNode
        while currentR:
           print("",currentR.val)
           currentR = currentR.rightChild
        while currentL:
            currentL = currentL.leftChild      
            print("",currentL.val)

My main:

zero = tree_node(0,None,None)
minusone = tree_node(-1,None,None)
one = tree_node(1,None,None)
minustwo = tree_node(-2,None,None)
two= tree_node(2,None,None)
bst = binary_tree(zero)
bst.addTreeNode(minustwo)
bst.addTreeNode(one)
bst.addTreeNode(two)
bst.addTreeNode(minusone)
bst.print_tree()

However when I try to call the addTreeNode() method it shows me a

Error: while current.rightChild and current.leftChild Attribute Error: 'NoneType doesn't have attribute rightChild'`.

If I flip the bst.addTreeNode(minustwo) with the bst.addTreeNode(minusone) line it prints 0 0 -1 -2 1 2 as it should so I suspect the issue is somewhere in these lines:

             if prev.val < treeNode.val < current.val:
                 prev.rightChild = treeNode
                 treeNode.rightChild = current
                 break

but I don't understand why it shouldn't it be this.

Answer 1

The main problem is that after assigning a new reference to current, your code does not first verify that this new reference is not None. It immediately performs a comparison with current.val. And so, if current happens to have become None by a previous assignment, this will bring about the error you got.

A similar problem will occur once the loop has finished -- you can see this from the while condition. Yet, right after the loop, your code accesses current.val again.

To fix this, completely remove those inner-most if blocks that start with if prev.val < treeNode.val < current.val: or similar. Besides that they access current.val without first ensuring current is not None, the rest of that if block replaces a subtree with the new node, which potentially destroys part of the tree. This makes no sense. Remove that code.

Also make sure that if current has received a new value, no other code executes, not even an if condition, before checking the while condition. So the second if should become an elif

And to fix the bug you have after the loop, you should use prev instead of current.

The corrected code:

    def addTreeNode(self,treeNode):
        current = self.baseNode
        prev = None
        while current:
            prev = current
            if treeNode.val < current.val:
                current = current.rightChild
            elif treeNode.val > current.val:
                current = current.leftChild
        if not prev:
            self.baseNode = treeNode    
        elif treeNode.val < prev.val:
            prev.rightChild = treeNode
        elif treeNode.val > prev.val:
            prev.leftChild = treeNode

I should probably also warn that your print_tree method is not correct. So I provide here an implementation that prints it sideways (90° rotated counter clockwise):

    def print_tree(self):
        def dfs(node, indent=""):
            if node:
                dfs(node.rightChild, "  " + indent)
                print(indent, node.val)
                dfs(node.leftChild, "  " + indent)
        dfs(self.baseNode)