Week 8

Binary Search Trees was the topic of week 8. BSTs are like an extended version of a basic binary tree, except you've got your insert() and find() method as well some specially designed classes called nodes with their own unique methods as well.

Nodes are the thing inside the BST that contain the object you want. A BST has left and right spots and by default they are None OR you can define a custom version of BST Node called BSTNoneNode or something similar to represent a Node that is null. By creating this empty Node class, you can avoid getting errors when searching through BSTs, because you won't be accessing a Node that doesn't exist.

BSTs use recursion to find items as well as calculate their maximum height. The lab we did, we were given 4 classes BST_rec.py and we implemented a method count_less(n) that counts number of items in BST less than n and returns that value.

Essentially, all 4 of the py files, we used recursion to create the count_less() method. I ended up creating one-liner count_less() methods and they were pretty efficient I'd say. My initial idea was to use ternary expressions to count items less than n.

For example, I don't know if a lot of people know this or not in our class, but I can convert boolean expressions to an integer by type casting them:

int(True) == 1 # This would return True because if you convert True to an integer, it becomes 1

Along with the above, ternary expressions proved most useful, because essentially, what the count_less() method returns is 1 or 0 along with a recursive call count_less() on both of its nodes (if they exist).