Welcome to Lesson 11!


Announcements
  • Quiz 4 next week
    • Trees, Binary Trees, Binary Search Trees
    • Hash Tables
  • Submit Project Report 2
  • Office Hour today at 1:30pm

Review Activities
  • What is the definition of a binary tree?
  • What is the definition of a binary search tree?
  • Are the below trees valid BSTs? Why or Why Not?
A.



B.




C.


Image source.

  • Draw the resulting BST from inserting the following values in this order into an empty tree: 8, 3, 4, 10, 12, 2, 11, 9, 6
  • What is the Big-O runtime of BST insert and search operations in the best, worst and average case?




Upcoming Assignments
  • Lab 6 due Tuesday
  • Quiz 4 on Thursday


~Have a Great Weekend!~