Week 9 - Binary Search Trees

Ah, BSTs. BSTs are great.  They're already organized so there are less cases to code for (yes I'm lazy, don't judge me), and searching them has a runtime of O(logn), how nice.

What exactly are BSTs? They're basically binary trees from all the way back in week 6 with one more pre-condition - in each node, the value of the root is greater than the left child and less than the right child.  Let's look at some visual examples of BSTs, again with my horrible drawings:

In the above, it may be surprising to note that I is indeed a binary search tree since it obeys the pre-condition that the left child must be less than the root and the right child must be greater than the root.  II is not a BST since 2 > 1.  III is also not a BST since each element in a binary search tree must be unique.  IV is a typical BST as we would expect.  V is also a BST since it follows the precondition.

The actual python implementation for BSTs is the same as normal binary trees, but we add the above stated pre-condition.

Note that the BST is actually a wrapper function of BSTNode so any methods made for BSTs need to be made as module level functions.  (See the insert function example from lecture).