Week 6 - Binary Search Trees

Learning objectives

  • Implement a Binary Search Tree
  • Use a stack to iterate through a BST

Day 1


Day 2

  • Start BSTs (Ch 31.4-31.6)
  • Do the BST WS and check against the key
  • Do Ch 31 Exercises - Find and Insert

Day 3

  • Continue with BSTs (Ch 31.7-31.10)
  • Do the BST Removal WS and check against the key
  • Do Ch 31 Exercises - Remove and Copy

Day 4

Trees

Ch 31.1-31.3 introduces trees. To build data structures, we will be mostly focusing on a special type of tree called a binary search tree (BST). But trees are useful as a model for solving many other kinds of problems. We first will briefly look at some of these other applications and general properties of trees before we dive into BSTs.

This video reviews the material:


BSTs

Read Ch 31.4-31.13.

The two Ch 31 exercises sets are appropriate after 31.5 (Find and Insert) and 31.9 (Remove and Copy) respectively.

The following videos review the material:

Ch 31.4-31.5 (BST Basics):


Ch 31.6-31.7 (BST Memory):


Ch 31.8-31.9 (BST Memory):


Ch 31.10 (BST Iteration):


BSTs and Lists and Treesort

This optional video discusses how a BST can be used to sort a list by transforming it into a tree and then back into a list: