CodeMonkey CodeMonkey - 3 months ago 8
Python Question

Python BST not working

I'm new to Python thus the question,this is the implementation of my my BST

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

def add(self, item):
return self.addHelper(item, self.root)

def addHelper(self, item, root):
if root is None:
root = Node(item)
return root

if item < root.data:
root.left = self.addHelper(item, root.left)
else:
root.right = self.addHelper(item, root.right)


This is the Node object

class Node(object):
def __init__(self, data):
self.data = data
self.left = None
self.right = None


This is my implmentation of str

def __str__(self):
self.levelByLevel(self.root)
return "Complete"



def levelByLevel(self, root):

delim = Node(sys.maxsize)
queue = deque()
queue.append(root)
queue.append(delim)
while queue:
temp = queue.popleft()
if temp == delim and len(queue) > 0:
queue.append(delim)
print()
else:
print(temp.data, " ")
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)


This is my calling client,

def main():
bst = BST()
bst.root = bst.add(12)
bst.root = bst.add(15)
bst.root = bst.add(9)

bst.levelByLevel(bst.root)


if __name__ == '__main__':
main()


Instead of the expected output of printing the BST level by level I get the following output,

9
9223372036854775807


When I look in the debugger it seems that the every time the add method is called it starts with root as None and then returns the last number as root. I'm not sure why this is happening.
Any help appreciated.

Answer

Based on the following, you can see that bst.root in None after the second call to add():

>>> bst.root = bst.add(12)
>>> bst.root
<__main__.Node object at 0x7f9aaa29cfd0>
>>> bst.root = bst.add(15)
>>> type(bst.root)
<type 'NoneType'>

You addHelper isn't returning the root node. Try this:

def addHelper(self, item, root):
    if root is None:
        root = Node(item)
        return root

    if item < root.data:
        root.left = self.addHelper(item, root.left)
    else:
        root.right = self.addHelper(item, root.right)

    return root

And then it works as expected:

>>> bst.root = bst.add(12)
>>> bst.root = bst.add(15)
>>> bst.levelByLevel(bst.root)
(12, ' ')
()
(15, ' ')
(9223372036854775807, ' ')
>>> bst.root = bst.add(9)
>>> bst.levelByLevel(bst.root)
(12, ' ')
()
(9, ' ')
(15, ' ')
(9223372036854775807, ' ')