trjhtr

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()

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?