CodeMonkey - 1 year ago 84

Python Question

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

`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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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, ' ')
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**