Lesson: Working with Binary Search Trees

In the previous lesson of this recursion and trees course, we learned to implement a binary heap and explored how heaps are helpful when querying a dataset. 

In this lesson, we’ll be implementing another special type of binary tree called a binary search tree. Binary search trees provide the ability to run efficient range queries on our datasets. Knowing how binary search trees work can help you understand the most efficient way to write a SQL query when using the WHERE clause.

As you work through the screens of this lesson, you’ll build a self-balancing binary search tree to demonstrate how to speed up range queries. You will also learn why you need a binary search tree to be self-balancing in order to the reduce the time complexity from O(n) to O(log n). 

At the end of this mission, you will build a query range method to query a CSV file for a range of data.

As with all of our lessons, in this lesson you’ll get to apply what you’ve learned from within your browser so that there's no need to use your own machine to do the exercises. The Python environment inside of this course includes answer checking so you can ensure that you've fully mastered each concept before learning the next concept.