# BST implementation (MIT OCW Runway scheduling problem) + Unit Testing in Python3

Inspired by MIT OCW (6.006)'s lecture on BSTs, I implemented them with the slight tweak where an element has to satisfy the "k-minute check" before insertion. If its value is within k of any other existing value in the node, the node should not be inserted. k is a positive integer parameter provided upon creation of the BST.

Apart from that I implemented the standard BST functionality of insert, find, delete_min, remove.

Things to critique:

1. I think my program is right (the tests say so?). However, testing can certainly be improved! How do I make better unit test cases?
2. Does the code follow PEP/Pythonic guidelines? What can I do to make my code closer to production code quality?
3. I made a function to print out the BST and use it as a visual means of debug, if need be. The problem is this then facilitates needing a debug flag (which Python doesn't really have). I ended up not really using it since the unit testing was sufficient in this case. Is a visual means of debugging like this strictly discouraged? Can it be implemented in unit testing?

Here's my implementation code schedule.py:

PRINT_ENABLED = False #this may not be the best approach to turn on/off flag for printing to stdout. Not production code material.

class Node():
"""
Representation of a Node in a BST
"""
def __init__(self, val : int):
# Create a leaf node with a given value
self.val = val
self.disconnect() # this is neat
def disconnect(self):
self.left = self.right = self.parent = None

class BST():
def __init__(self, k_value, current_time):
self.root = None
self.k = k_value
self.current_time = current_time
super().__init__()

def k_min_check_passed(self, booked : int, requested : int) -> bool:
"""
Check if the requested time value is a valid time entry (> current time) within k min of booked request's time value
Return false (failure) if it is, and true if not.
"""
if requested <= self.current_time or (requested <= booked + self.k and requested >= booked - self.k):
return False
else:
return True

def insert(self, t : int) -> Node:
"""
Insert a node with value t into the tree, returning a ptr to the leaf
If the k minute check is violated, don't insert & return None
"""
new_node = Node(t)
if self.root is None:
self.root = new_node
else:
curr = self.root
while True:
val = curr.val
# Check it the k-min invariant is held for every node.
# If it fails, there's no point in inserting.
if self.k_min_check_passed(val, t) == False:
return None
if t < val:
if curr.left is None:
curr.left = new_node
new_node.parent = curr
break
curr = curr.left
else:
if curr.right is None:
curr.right = new_node
new_node.parent = curr
break
curr = curr.right
return new_node

def find(self, t : int) -> Node:
"""
Search for a key in the tree and return the node. Return None otherwise
"""
node = self.root
while node is not None:
val = node.val
if t == val:
return node
elif t < val:
node = node.left
else:
node = node.right
return None

def delete_min(self) -> Node:
"""
Delete the minimum key. And return the old node containing it.
"""
old = self.root
while old is not None:
if old.left is None:
if old.parent is not None:
old.parent.left = old.right
else:
#remove root
self.root = old.right
if old.right is not None:
old.right.parent = old.parent
old.disconnect()
break
old = old.left
return old

def remove(self, t : int) -> Node :
"""
Given a node value t, removes the node
from the BST, restructuring the tree
in the case where the node has children.
If the node to be deleted has both non-null children,
then the node's left child becomes the node's parent's
new child, and the node's right child subtree becomes
the left child's rightmost descendant.

Returns the deleted node.
If the node to be deleted does not exist, returns None
"""
node = self.find(t)
if node is None:
return None
# Case 1: node has 2 children
if node.left is not None and node.right is not None:
# find right most node of the current node's left child's subtree
rleaf = node.left
while rleaf.right is not None:
rleaf = rleaf.right
# then swap the leaf and the current node values
temp = rleaf.val
rleaf.val = node.val
node.val = temp
# delete the leaf node we found (that has current node's value)
# and make its left child the right child of its parent
if rleaf.parent is not None:
# determine the leaf's relationship with its parent
rleaf_is_left_child = (rleaf == rleaf.parent.left)
if rleaf_is_left_child:
rleaf.parent.left = rleaf.left
else:
rleaf.parent.right = rleaf.left
if rleaf.left is not None:
rleaf.left.parent = rleaf.parent
rleaf.disconnect()
else:
# check elif syntax implications here
if node.parent is None:
# remove the root and appoint the new root
# Case 2: node has only right child
if node.right is None and node.left is None:
self.root = None
elif node.left is None:
node.right.parent = None
self.root = node.right
elif node.right is None:
node.left.parent = None
self.root = Node.left
node.disconnect()
else:
# determine the nodes's relationship with its parent
node_is_left_child = (node == node.parent.left)
# Case 2: node has only right child
if node.left is None:
if node_is_left_child:
node.parent.left = node.right
else:
node.parent.right = node.right
if node.right is not None:
node.right.parent = node.parent
node.disconnect()
# Case 3: node has only left child
elif node.right is None:
if node_is_left_child:
node.parent.left = node.left
else:
node.parent.right = node.left
if node.left is not None:
node.left.parent = node.parent
node.disconnect()
return node

def print_BST(root : Node):
"""
Given a pointer to a root node of a BST (sub)Tree,
Prints the level order traversal of that subtree as a list of nodes' values.
Nodes that are null are incdicated as N.
If a node was null in the previous level, it's children will not exist
and the nodes are not considered in the list.
"""
print ('[', end=' ')
q = []
q.append(root)
while q:
front = q.pop(0)
# break
if front is None:
print ('N', end=' ')
else:
print(front.val, end=' ')
q.append(front.left)
q.append(front.right)
print(']\n')

def test_printing():
root = Node(3)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.right.left = Node(4)
print_BST(root)
if __name__ == "__main__":
if PRINT_ENABLED:
test_printing()


And my unit test code test.py:

import unittest
import sys, os
sys.path.append(os.path.abspath('..')) #this was a workaround I found to avoid ModuleNotFoundErrors, but now I need to mandatorily run tests from ../
from runway_scheduling.src.schedule import BST, Node

class TestBST(unittest.TestCase):
def setUp(self):
super().setUp()
TEST_K_VAL = 1
CURRENT_TIME = 0
self.tree = BST(TEST_K_VAL, CURRENT_TIME)
self.nums = [3, 1, 5, 9, 7]
for t in self.nums:
self.tree.insert(t)
self.rt_node = self.tree.root

def test_k_min_check(self):
vals = self.nums
# 2 things: 1) I don't like writing magic numbers, is there a better way to do this?
#           2) I only test the functionality of the k-min check over here
#              I test whether insert checks it each time (for all nodes) in insert. Is this a good approach
self.assertFalse(self.tree.k_min_check_passed(vals[0], -1))
self.assertFalse(self.tree.k_min_check_passed(vals[3], 10))
self.assertTrue(self.tree.k_min_check_passed(vals[-1], 5))

def test_insert(self):
self.assertEqual(self.rt_node.val, self.nums[0]) #check root (initially None) has been correctly inserted
self.assertEqual(self.rt_node.left.val, self.nums[1]) #check left node
self.assertEqual(self.rt_node.left.right, None) #is this test necessary?
self.assertEqual(self.rt_node.right.right.left.val, self.nums[-1]) #Again, I don't think this is a "good" test
# check k min property is applied correctly
self.assertIsNone(self.tree.insert(4))
self.assertIsNotNone(self.tree.insert(11))

def test_find(self):
self.assertEqual(self.tree.find(7), self.rt_node.right.right.left)
self.assertEqual(self.tree.find(4), None)

def test_delete_min(self):
min_key = self.rt_node.left.val
self.assertEqual(self.tree.delete_min().val, min_key) #we should have got back the deleted node
self.assertEqual(self.rt_node.left, None) #the pointer to left child should have been modified
old_root_val = self.rt_node.val
old_root_right_val = self.rt_node.right.val
self.assertEqual(self.tree.delete_min().val, old_root_val) #handled corner case of root being minimum
self.assertEqual(self.tree.root.val, old_root_right_val) #check the root has been updated.

def test_remove(self):
"""
Testing the arbitrary deletion of any specified node
The following test cases exist:
1) Node to be deleted does not exist
2) Node has 2 children:
a) Node is parent's left or right child
b) Node is the root
3) Node has Left Child Only:
a) Node is parent's left child
b) Node is parent's right child
c) Node is the root
4) Node has Right Child Only:
a) Node is parent's left child
b) Node is parent's right child
c) Node is the root
5) Node has no Children
6) Only node in the tree
"""
# CASE 1)
NON_EXISTANT_VAL = 100
self.assertIsNone(self.tree.remove(NON_EXISTANT_VAL))

# CASE 2b)
# 1 (nums[1]) should be the new root
self.tree.remove(3)
self.assertEqual(self.tree.root.val, 1)

# CASE 3b)
self.assertEqual(self.tree.remove(self.nums[3]).val, 9)
self.assertEqual(self.tree.root.right.right.val, 7)

# CASE 4c)
self.tree.remove(1)
self.assertEqual(self.tree.root.val, 5)

# CASE 5, 4b)
self.tree.remove(7)
self.assertIsNone(self.tree.root.left)

# CASE 2a)
# insert two children with subtrees
self.tree.insert(50)
self.tree.insert(10)
self.tree.insert(20)
self.tree.insert(30)
self.tree.insert(70)
self.tree.insert(65)
# The tree should now be:
# [{5}, {N, 50}, {10, 70}, {N, 20, 65, N}, {N, 30, N, N} ]
# (when read as level order traversal)
self.tree.remove(50)
self.assertEqual(self.tree.root.right.val, 30)

# CASE 4a)
self.tree.remove(10)
self.assertEqual(self.tree.root.right.left.val, 20)

# CASE 3a,c)
self.tree.remove(5)
self.tree.remove(70)
self.tree.remove(65)
self.tree.remove(20)
self.assertIsNone(self.tree.root.right)
# CASE 6
self.tree.remove(30)
self.assertIsNone(self.tree.root)

def tearDown(self):
self.nums = []
while (self.tree.root is not None):
self.tree.delete_min()
super().tearDown()

if __name__ == "__main__":
unittest.main()


Any feedback is welcome, thank you!

EDIT: My directory structure is something like:

../
| - src : contains schedule.py
| - test: contains test.py


The ModuleNotFoundErrors occured when I didn't add that line, and imported BST and Node from runway_scheduling.src.schedule. There's a few similar Qs on SO, so I'm going over them rn to see if they apply but that was a quick fix I had made - something I'd like to remedy. I tried adding __init__.py files, but that didn't really help.

• Please edit your question to show a full directory tree for your project. Something about your module structure is fishy. – Reinderien May 26 '20 at 17:37
• Use tox or nox with a setuptools package. Not the silly sys.path.append(os.path.abspath('..')) hack. – Peilonrayz May 26 '20 at 17:49

## Debug prints

I made a function to print out the BST and use it as a visual means of debug, if need be. The problem is this then facilitates needing a debug flag (which Python doesn't really have). I ended up not really using it since the unit testing was sufficient in this case. Is a visual means of debugging like this strictly discouraged?

[...]

this may not be the best approach to turn on/off flag for printing to stdout. Not production code material.

Indeed! This is the perfect use case for the logging module. Leave all of your print statements in but convert them to logging calls at the debug level. Then, by changing only the level of the logger you will be able to show or omit that content.

## Non-init attribute set

self.disconnect() # this is neat


The problem with this approach is that there are attributes being set that are not done directly in the __init__ function. Some linters, including PyCharm's built-in linter, will call this out. Consider moving initialization of those three attributes to the constructor, with type hints indicating what actually goes in there - possible Optional['Node'].

## Boolean expressions

    if requested <= self.current_time or (requested <= booked + self.k and requested >= booked - self.k):
return False
else:
return True


can be (if I've done my boolean algebra correctly)

return (
requested > self.current_time and not (
-self.k <= requested - booked <= self.k
)
)


## Unit tests

You ask:

Are the unit testcases I came up with satisfactory, or need more work?

About this:

sys.path.append(os.path.abspath('..')) #this was a workaround I found to avoid ModuleNotFoundErrors, but now I need to mandatorily run tests from ../


That's spooky and should be unnecessary. Normal unit test discovery should work fine as long as you run from the "sources-root" of your project. Incidentally, src as a module name is a sign that your module paths are wonky. BST should be in runway_scheduling.schedule, and TestBST should be in something like runway_scheduling/tests/test_bst.py. I can't comment any further without seeing your directory structure.

You also write:

I don't like writing magic numbers, is there a better way to do this?

Tests are somewhat of an exception in my mind. Having everything be explicit and in-place is actually a good thing. The only thing I can suggest, although I don't immediately see where it would be applicable, is subTest - you can find code that is repetitive with only numerical changes, factor out those numerical changes to tuples, and write a parametric loop with a subtest.

• 1) The logging option seems to be exactly what I was looking for! 2) Interesting, and I didn't consider this. I think i will add the None initializations to the init function, and keep the disconnect as a member function which I use anyways for removal of nodes. I was using VSCode, so I guess my linter didn't complain. 3) That definitely looks cleaner, and something I can get in the habit of editing such code. Awesome, thanks for the great feedback! Are the unit testcases I came up with satisfactory, or need more work? – cloudy_eclispse May 26 '20 at 16:30
• I was using VSCode, so I guess my linter didn't complain - indeed; professionally, I use PyCharm because I find its static analysis to be more thorough. – Reinderien May 26 '20 at 17:14
• Are the unit testcases I came up with satisfactory, or need more work? - edited. Overall they're quite good. – Reinderien May 26 '20 at 17:26
• p.s. a more quantitative answer to this is "run a coverage tool". – Reinderien May 26 '20 at 17:35
• I improved my directory structure and unittest discover (which I didn't know existed, lol) works, so thanks! – cloudy_eclispse May 27 '20 at 19:57