# Python beginner's tree with unit tests

I have implemented a tree in Python. However, due to my lack of experience with Python, I am not able to judge the overall quality of my code.

import unittest
from datetime import *
from gc import *

RET_NO = 0
RET_YES = 1
RET_MAYBE = 0.5 # haha :)

class Tree(object):
"""
Mutable abstract data type for arbitrary data with O(N) access on elements.
"""
def __init__(self):
super(Tree, self).__init__()
self.root = None

def insert(self, element):

if self.root:
self.root.insert(element)
else:
self.root = Node(element)

def contains(self, element):
if self.root is None:
print 'WARN: Contains() called before elements were inserted!!'
raise Exception()

return self.root.contains(element) if self.root else RET_NO

def size(self):
return self.root.size() if self.root else 0

def bulk_insert(self, elements=[]):
while len(elements):
self.insert(element[0])
elements = elements[1:]

class Node(object):
"""
Node class to be used in Tree instances.
"""
def __init__(self, element):
super(Node, self).__init__()
self.element = element
self.left = None
self.right = None

def insert(self, element):
if self.element == element:
return
if element < self.element:
if self.left:
self.left.insert(element)
else:
self.left = Node(element)
else:
if self.right:
self.right.insert(element)
else:
self.right = Node(element)
raise Exception('Should never reach this line!')

def contains(self, element):
if self.element == element:
return RET_YES
if element < self.element:
if self.left:
return self.left.contains(element)
else:
return RET_NO
else:
if self.right:
return self.right.contains(element)
else:
return RET_NO
raise Exception('Should never reach this line!')

def size(self):
"""
Return size
"""
left_size = self.left.size() if self.left else 0
right_size = self.right.size() if self.right else 0
return left_size + right_size + 1

class TreeTest(unittest.TestCase):

def setUp(self):
# no setup required yet
pass

def tearDown(self):
# leave memory in a clean state
gc.collect()

def test_1(self):
#tree = Tree()
#self.assertEqual(tree.size(), 0)
#tree.insert(10)
#self.assertEqual(tree.size(), 10)
self.assertTrue(True)

def test_2(self):
start = datetime.now()

elements = []
for i in range(1000000):
elements += [i]

tree = Tree()
# tree should be empty
for i in elements:
self.assertEqual(tree.contains(i), RET_NO)
# fill tree
for i in elements:
tree.insert(i)
# tree should be full
for i in elements:
self.assertEqual(tree.contains(i), RET_YES)

end = datetime.now()
elapsed = end - start
# must not take longer than a minute
self.assertTrue(elasped.total_seconds() < 60)

def test_3(self):
tree = Tree()
try:
tree.contains(1)
# should have thrown an exception -> test failed
self.assertTrue(False)
except Exception, ValueError:
# expected to raise an Exception -> test should pass
self.assertTrue(True)


1. Don't do from something import *.

Either import what you need:

from datetime import datetime


Or import the entire module and use qualified names:

import datetime
...
start = datetime.datetime.now()


Importing everything is dangerous because it can shadow already existing names. One such example:

import datetime
from datetime import *
# datetime as a class shadows datetime as a module


You might want to do a little reading on the subject.

1. This whole thing makes no sense:

RET_NO = 0
RET_YES = 1
RET_MAYBE = 0.5 # haha :)


Instead of RET_YES / RET_NO you sould use True and False.

1. You don't have to call super(...).__init__ if the class only inherits from object.

1. Why do you print something to stdout and then raise an empty exception?

print 'WARN: Contains() called before elements were inserted!!'
raise Exception()


you should do

raise Exception('contains() called on empty tree')


1. In the method Tree.contains, you already checked if self.root is None, so this

return self.root.contains(element) if self.root else RET_NO


can be simplified to this

return self.root.contains(element)


1. Instead of contains you can define the __contains__ method. Then you can use the in keyword:

return element in self.root


Although in this particular case it's less readable, so it's probably better to just stick with contains.

1. Method Tree.bulk_insert is just wrong. There's no point in having an empty list for a default argument. In the for loop you modify the list while iterating over it, and on each iteration you call the len function. Why? Even the C-style

for i in range(len(elements)):
self.insert(elements[i])


would have been better.

This is the way to do it in Python:

def bulk_insert(self, elements):
for element in elements:
self.insert(element)


That way elements doesn't have to be a list, it can be any iterable.

1. Does your tree have a special requirement that it cannot contain the same element twice? If not, then in Node.insert there should be no

if self.element == element:
return


1. Remove unreachable statements. There's no point in having

raise Exception('Should never reach this line!')


in Node.contains, while having it in Node.insert effectively makes the method raise an exception in almost all cases. Actually if you fix the error mentioned in the previous point, it would be in completely all cases.

1. The comment

"""
Return size
"""


is pointless. The method itself is called size, so it's obvious that it returns size. Also, the name size is quite ambiguous to begin with. Either don't restate code in comments, or actually explain what the method does (eg. how do you compute the size). A more suitable name would be number_of_elements, or maybe something shorter but descriptive like nelems.

1. The docstring of Node states:

"""
Node class to be used in Tree instances.
"""


I'd say it can possibly be used in other classes than Tree, so don't create a tight coupling between the two, even if it's just in comments.

1. size can be a property:

@property
def size(self):
...


That way you won't have to call it:

left_size = self.left.size if self.left else 0


1. Even tests should be documented. Add docstrings explaining what do the test_* methods test. Your non-test code also lacks documentation.

1. The docstring of Tree says "O(N) access on elements". This is not quite true, for two reasons:
• your Tree and Node classes don't even allow you to access elements, they only allow you to check whether an element is present in the tree,
• $O(n)$ is the worst case; average asymptotic complexity is $O(log(n))$.

1. Have you by chance forgotten to implement a remove method? Or you just wanted an insert-only tree?

$$⸻$$