Creating a BST and insert function in Python

Question

I have created a BST using Python and am having issues with the insert function. I can insert one value, but then when I try to insert again it does not work properly. In particular, I get an error on the _insert function that there is no data attribute for a Nonetype object, although the object should be the created root. Here is my implementation:

class Node:
    def __init__(self, data, left=None, right=None):
        self.data=data
        self.left=left
        self.right=right        
    def setdata(self,data):
        self.data=data
    def hasLeft(self):
        return self.left 
    def hasRight(self):
        return self.right
class BST():
    def __init__(self):
        self.root=None
    def insert(self, data):
        if self.root:
            self._insert(data, self.root)
        else:
            self.root=Node(data)

    def _insert(self, data, curr):
        if data<curr.data:
            if curr.hasLeft:
                self._insert(data, curr.left)
            else:
                curr.left=Node(data)
        if data>curr.data:
            if curr.hasRight:
                self._insert(data, curr.right)
            else:
                curr.right=Node(data)

tree=BST()
print tree.root
tree.insert(1)
print tree.root.data
tree.insert(3) # error occurs here
print tree.root.data

Traceback:

Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    tree.insert(3)
  File "<pyshell#3>", line 6, in insert
    self._insert(data, self.root)
  File "<pyshell#3>", line 18, in _insert
    self._insert(data, curr.right)
  File "<pyshell#3>", line 11, in _insert
    if data<curr.data:
AttributeError: 'NoneType' object has no attribute 'data'

I notice you've opened a new question; did my answer help? – jonrsharpe Nov 06 '14 at 19:54 — jonrsharpe, Nov 06 '14 at 19:54

score 0 · Accepted Answer · edited May 23 '17 at 10:33

The traceback shows you what happens:

tree.insert(3)

Your starting call; so far, so good. if self.root: (note: should be if self.root is not None:, see e.g. this answer) evaluates truthy, so it calls:

self._insert(data, self.root)

here data > curr.data and curr.hasRight both evaluate truthy. Why?! Because you aren't calling the method; although the return value of that method would evaluate falsey, the method itself doesn't.

That should be:

if curr.hasRight() is not None:
              # ^ note parentheses 
                 # ^ and use of 'is' again

After that, as curr.right is None,

self._insert(data, curr.right)

is bound to fail, as curr will be None:

    if data<curr.data:
AttributeError: 'NoneType' object has no attribute 'data'

right on cue.

Note that it would be neater to handle None properly in Node, too, making hasLeft and hasRight return boolean, rather than the node or None:

def hasLeft(self):
    return self.left is not None

then in BST, simply:

if curr.hasLeft():

Creating a BST and insert function in Python

1 Answers1