MISSION 231

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.

Objectives

  • How to build and run a BST.
  • Determine when to use a binary search tree over a heap.
  • Discover the runtime of binary search tree algorithms.

Mission Outline

1. Introduction to the BST
2. Insert Multiple and Sorted Order
3. Searching the BST
4. Why We Need a Balanced BST
5. Maintaining a Balance (Part 1)
6. Maintaining a Balance (Part 2)
7. Maintaining a Balance (Part 3)
8. Enhancing the Node and BST Class
9. Adding the Range Query
10. Range Querying a CSV
11. Next Steps
12. Takeaways

recursion-and-tree-structures

Course Info:

Advanced

The median completion time for this course is 5.2 hours. View Details

This course requires a premium subscription. This course includes six missions and one guided project.  It is the sixth course in the Data Engineer path.

START LEARNING FREE

Take a Look Inside