Binary Search Tree Example

To continue with the use of the properties of Binary Search Trees. The best example would be a lab exercise that was initially quite challenging but finally clarified many misconceptions about BSTs and left me with in-depth understanding (or at least, that's how I feel)!

For lab 8, we had to write a method called count_less, where given a BST the function returns a sum of all the numbers less than the value at the root. We had to write this method using three different class implementations but the one I present here is the one I struggled with the most.

def count_less(self: '_BSTNode', item: object) -> int:
        """
        Return the number of items in the BST rooted at this node that are
        strictly less than item.
        """
        if self.item:
            if self.left is None and self.right is None:
                if self.item < item:
                    return 1
                else:
                    return 0
            elif self.left is None:
                if self.item < item:
                    return 1
                else:
                    return self.right.count_less(item)
            elif self.right is None:          
                if self.item < item:
                    return self.left.count_less(item) + 1
                else:
                    return self.left.count_less(item)
            else:
                if self.item < item:
                    return self.left.count_less(item) + 1
                else:
                    return self.left.count_less(item) + self.right.count_less(item)
        else:
            return 0

Yes, I know that that my code is really long because of repetition but I am presenting this version instead of a compact one for the sake of clarity as I describe how the property of BST is used when coding this method.

First of, assuming that the class BSTNode is implemented properly, we check if the root of the tree has a value and if it does then we check if it has no children, only left child, only right child or both children. The case where we have no children, the implementation is straight forward. Also, for the case where we have no left child, we are bound to check the right child given the value of the item is more than the value of the root, and vice versa for the case where we have no right child. However, it is interesting to take a look at the else clause because this is where we see the implementation of a BST property. In the else clause, given the value of the item is less than the value of the root, we only do recursion on the left subtree because that is the only place where there could be more values that are less than the value of the item to suffice the purpose of this function.