Lesson 6.1: Level Order Traversal + the Dictionary/Map ADT
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 6.1-levelorder-dict-bst-203-1221.pdf Download 6.1-levelorder-dict-bst-203-1221.pdf | PDF Download PDF |
On Cloud Recordings under Canvas Zoom tab after class |
| 1–2PM | 6.1-level-order-dict-adt-1pm.pdf Download 6.1-level-order-dict-adt-1pm.pdf | 6.1-level-order-dict-adt-1pm-annotated.pdf Download 6.1-level-order-dict-adt-1pm-annotated.pdf |
On Cloud Recordings on Canvas Zoom |
| 4–5PM | 6.1-level-order-dict-adt-4pm.pdf Download 6.1-level-order-dict-adt-4pm.pdf | 6.1-level-order-dict-adt-4pm-annotated.pdf Download 6.1-level-order-dict-adt-4pm-annotated.pdf |
On Cloud Recordings on Canvas Zoom |
Readings:
- Carrano & Henry: Chapter 15.1 (Tree Terminology)
- Carrano & Henry: Chapter 15.2 (Binary trees and traversal)
Summary:
We introduce a new, non-recursive traversal, and we discuss a new abstract data type (ADT) that we can implement with linked lists and arrays and soon with trees!
Learning Outcomes:
- Analyze running time of recursive traversal, and prove the analysis correct.
- Execute, implement, and analyze, level-order traversal.
- Define the Dictionary ADT (also known as Map ADT), including its insert, find, and remove operations.
- Justify bounds on runtime of each Dictionary operation for linked lists, unsorted arrays, and sorted arrays.