if __name__ == '__main__':
import unittest, random
class TestBST(unittest.TestCase):
def test_random_lists(self):
"""Test a bunch of lists of various sizes, randomly"""
for length in range(20):
bst = new BST()
lst = [ random.randint(1, 100) for _ in range(length) ]
with self.subTest(lst=lst):
for val in lst:
bst.put(val)
lst.sort()
self.assertEqual( bst.inorder_list(), lst)
unittest.main()
if __name__ == '__main__':
import unittest, random
class TestBST(unittest.TestCase):
def test_random_lists(self):
"""Test a bunch of lists of various sizes, randomly"""
for length in range(20):
bst = new BST()
lst = [ random.randint(1, 100) for _ in range(length) ]
with self.subTest(lst=lst):
for val in lst:
bst.put(val)
lst.sort()
self.assertEqual( bst.inorder_list(), lst)
unittest.main()
if __name__ == '__main__':
import unittest, random
class TestBST(unittest.TestCase):
def test_random_lists(self):
"""Test a bunch of lists of various sizes, randomly"""
for length in range(20):
bst = BST()
lst = [ random.randint(1, 100) for _ in range(length) ]
with self.subTest(lst=lst):
for val in lst:
bst.put(val)
lst.sort()
self.assertEqual( bst.inorder_list(), lst)
unittest.main()
class Node:
It is "strange" to have a Node with no value. Consider removing the default value=None.
You never create a Node with an explicit "left" or "right" branch. Consider removing these extra parameters from the constructor, and just assigning them to None.
Private members should be prefixed by an underscore. Since no external entity should access the value, or the left or right branches, these should be renamed.
class Node:
def __init__(self, value):
self._value = value
self._left = None
self._right = None
Node is actually an internal detail of BST, so perhaps nest it as an inner class:
class BST:
class _Node:
def __init__(self, value):
self._value = value
self._left = None
self._right = None
Again, a node with no value is "strange". It is much more common to represent an empty tree with as root=None, rather than root=Node(None).
def __init__(self):
self._root = None
Your put() method calls _put(), which can call _put(), which can call _put() and so on. In short, it is recursive. There is no need to be recursive; you never need to return a value from a sub-call. You are using tail-recursion, so the compiler/interpreter might simply jump back to the top of the function, instead of creating additional stack-frames. Except python doesn't do tail recursion, and you could get a stack overflow!
Instead, you can simply do the loop yourself:
def put(self, value):
new_node = BST._Node(value)
if self._root:
node = self._root
while node:
prev = node
node = node._left if value < node._value else node._right
if value < prev._value:
prev._left = new_node
else:
prev._right = new_node
else:
self._root = new_node
Ditto for contains(). Don't rely on tail-recursion, just create the loop yourself.
def contains(self, value):
node = self._root
while node:
if node._value == value:
return True
node = node._left if value < node._value else node._right
return False
In-order traversal: building lists is so passé. Generators can be much more efficient. Starting with Python 3.3, we also get the cool new yield from syntax, to make them easier:
def inorder(self):
def _inorder(node):
if node._left:
yield from _inorder(node._left)
yield node._value
if node._right:
yield from _inorder(node._right)
if self._root:
yield from _inorder(self._root)
If you want to return a list, and not the generator, you could simply pass the generator to the list() function.
def inorder_list(self):
return list(self.inorder())
Avoid polluting the global namespace. I prefer my tests in a separate "xxxx_test.py" file, but for a single file solution, you can put the required imports and test classes in the if __name__ == '__main__': block:
if __name__ == '__main__':
import unittest, random
class TestBST(unittest.TestCase):
def test_random_lists(self):
"""Test a bunch of lists of various sizes, randomly"""
for length in range(20):
bst = new BST()
lst = [ random.randint(1, 100) for _ in range(length) ]
with self.subTest(lst=lst):
for val in lst:
bst.put(val)
lst.sort()
self.assertEqual( bst.inorder_list(), lst)
unittest.main()
Finally, documentation! Use """docstrings"""
Run help(BST) and look at the output. Is everything documented? Are there any unnecessary (ie, private) classes or methods exposed to the outside world?