# BST implementation in Python

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.

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

• there are actually a few ways to accomplish this structure, I'd recommend searching around the internet and looking at all the other different implementations. I personally would construct something that acts like an object with the built in __iter__ functionality, which would allow me to have the object act more like a collection/list and easily iterate it. – C. Harley Aug 2 '18 at 5:09

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?