Week 07 Binary Search Trees

This week we will combine binary search with linked lists to create binary search trees. We learned in past weeks that linear search of a linked list is an O(N) operation. We also learned that binary search could find an element in a sorted list stored sequentially in an array. The binary search operation is an O(log2N) operation. It would be nice if we could use binary search with linked lists, however, how do we find the midpoint of a linked list of nodes? It turns out that there is no practical way of doing this, however, we can reorganize the list's elements into a linked structure that is perfect for binary search: the binary search tree.