Python beginner's tree with unit tests

Question

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)

Answer 1

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.

---

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

---

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

---

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

   Instead of

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

   you should do

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

---

5. 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)
   

---

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

---

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

---

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

---

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

---

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

---

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

---

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

---

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

---

14. 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))\$.

---

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

$$⸻$$