Reminder that you must complete the pre-reading before each class.

On this page:
✔️ Pre-reading for Tuesday 3/30
✔️ Pre-reading for Thursday 4/1

---

Pre-Reading for BST Analysis, Tuesday 3/30

Essential Questions

Before attending class, please complete the material below and use the following questions to guide your note-taking:

✔️ What is the average and worst time complexity of inserting into a BST?
✔️ What is the average and worst time complexity of deleting from a BST?
✔️ What is the average and worst time complexity of searching a BST?

Read/Watch/Review

Before attending class, please complete the material below:

• Read BST Analysis
  • Note that the worst-case given assumes a balanced tree; ideally want to define in terms of height rather than nodes (since height will give us a more accurate answer). Watch video below to understand time complexity in terms of height.
• Watch Time Complexities of Binary Search Trees Operations (10 min)

In Class

In today’s class we’ll be reviewing and applying BST Analysis concepts, as well as reviewing Final Project info.

---

Pre-Reading for BST Implementation, Thursday 4/1

Essential Questions

✔️ What’re the steps necessary to insert an element into a BST?
✔️ What’re the steps necessary to delete an element from a BST?
✔️ What’re the steps necessary to search for an element in a BST?
✔️ What’re the steps necessary to determine the height of a BST?
✔️ What’re the steps necessary to determine if a BST is full or complete?

Read/Watch/Review

Before attending class, please complete the material below:

• Read the Lab 10 Handout
• Watch Binary Search Trees (BST) Explained in Animated Demo (6 min)
• Review the slides from Tuesday’s class (for height)
• Review the Lab 9 Handout (for fullness and completeness)

In Class

In today’s class we’ll be continuing to work on our lab’s BST implementation.