I was asked to perform the following tasks at one of the technical interviews. I did the BST implementation in python. I think the solution passed all of the solution. I broke down the tasks in the following bulletin:
# 1) initilize the binary Search tree
# 2) Implement the "put" and "contains" methods with helper function
# 3) Test the "inOrderTraversal" method.
# 4) Add additional relevant tests
import unittest
class BST(object):
def __init__(self):
self.root = Node()
def put(self, value):
self._put(value, self.root)
def _put(self, value, node):
if node.value is None:
node.value = value
else:
if value < node.value:
if node.left is None:
node.left = Node()
self._put(value, node.left)
else:
if node.right is None:
node.right = Node()
self._put(value, node.right)
def contains(self, value):
return self._contains(value, self.root)
def _contains(self, value, node):
if node is None or node.value is None:
return False
else:
if value == node.value:
return True
elif value < node.value:
return self._contains(value, node.left)
else:
return self._contains(value, node.right)
def in_order_traversal(self):
acc = list()
self._in_order_traversal(self.root, acc)
return acc
def _in_order_traversal(self, node, acc):
if node is None or node.value is None:
return
self._in_order_traversal(node.left, acc)
acc.append(node.value)
self._in_order_traversal(node.right, acc)
class Node(object):
def __init__(self, value=None, left=None, right=None):
self.value = value
self.left = left
self.right = right
class TestBST(unittest.TestCase):
def setUp(self):
self.search_tree = BST()
def test_bst(self):
self.search_tree.put(3)
self.search_tree.put(1)
self.search_tree.put(2)
self.search_tree.put(5)
self.assertFalse(self.search_tree.contains(0))
self.assertTrue(self.search_tree.contains(1))
self.assertTrue(self.search_tree.contains(2))
self.assertTrue(self.search_tree.contains(3))
self.assertFalse(self.search_tree.contains(4))
self.assertTrue(self.search_tree.contains(5))
self.assertFalse(self.search_tree.contains(6))
self.assertEqual(self.search_tree.in_order_traversal(), [1,2,3,5])
def test_empty(self):
self.assertEqual(self.search_tree.in_order_traversal(), [])
def test_negative(self):
self.search_tree.put(-1)
self.search_tree.put(11)
self.search_tree.put(-10)
self.search_tree.put(50)
self.assertTrue(self.search_tree.contains(-1))
self.assertTrue(self.search_tree.contains(11))
self.assertTrue(self.search_tree.contains(-10))
self.assertTrue(self.search_tree.contains(50))
self.assertEqual(self.search_tree.in_order_traversal(), [-10,-1,11,50])
def test_dupes(self):
self.search_tree.put(1)
self.search_tree.put(2)
self.search_tree.put(1)
self.search_tree.put(2)
self.assertTrue(self.search_tree.contains(1))
self.assertTrue(self.search_tree.contains(2))
self.assertEqual(self.search_tree.in_order_traversal(), [1,1,2,2])
def test_none(self):
self.search_tree.put(None)
self.assertFalse(self.search_tree.contains(None))
self.assertEqual(self.search_tree.in_order_traversal(), [])
if __name__ == '__main__':
unittest.main()
1 Answer 1
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 = 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?
__iter__functionality, which would allow me to have the object act more like a collection/list and easily iterate it. \$\endgroup\$