Outline:

1. Questions?
2. Binary search trees, cont’d
   • recap: inserting into a BST
   • example implementation: BinarySearchTree.kt
   • deleting from a BST
     • simple case
     • complex case
   • operation time complexity
   • why use a BST?
3. Prefix trees (a.k.a. “Tries”)
   • basic idea
   • example implementation: PrefixTree.kt
4. Wrap-up

What’s next

Upcoming assignments/events:

• Assignment 6 will be released later today, and is all about trees!
• CS Bits & Bytes this week features Dr. Betty Cheng, a professor at Michigan State University, talking about trustworthy AI – attend the talk and write up two paragraphs to earn a token for an extra assignment resubmission

What you should do now:

• The readings (see below)
• Submit Assignment 5
• Attempt Part A of Assignment 6 – it’ll be online soon

Reading assignment (to be completed by the next class):

Prefix trees (from today):

• Prefix trees (a.k.a. “tries”)

Sorting (for next time):

• Mergesort concepts
• Mergesort implementation
• Quicksort