4
\$\begingroup\$

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

enter image description here

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.

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

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.

\$\endgroup\$
6
  • \$\begingroup\$ 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? \$\endgroup\$ – cloudy_eclispse May 26 '20 at 16:30
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Reinderien May 26 '20 at 17:14
  • 1
    \$\begingroup\$ Are the unit testcases I came up with satisfactory, or need more work? - edited. Overall they're quite good. \$\endgroup\$ – Reinderien May 26 '20 at 17:26
  • 1
    \$\begingroup\$ p.s. a more quantitative answer to this is "run a coverage tool". \$\endgroup\$ – Reinderien May 26 '20 at 17:35
  • 1
    \$\begingroup\$ I improved my directory structure and unittest discover (which I didn't know existed, lol) works, so thanks! \$\endgroup\$ – cloudy_eclispse May 27 '20 at 19:57

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.