1
\$\begingroup\$

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()
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ – C. Harley Aug 2 '18 at 5:09
3
\$\begingroup\$

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?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.