In this lecture, we'll introduce trees as a new linked data struture and learn about different ways of traversing them.
- Readings: Text 16.1
- Lecture quiz on Canvas
Today was mostly a conceptual lecture. We discussed a LOT of tree-related terminology. We also saw binary search trees (BSTs) for the first time and discussed best-, worst-, and average-case runtimes for insertion and search in BSTs. (A discussion of the deletion algorithm is postponed until next time.)
We concluded our lecture with four tree traversal algorithms: pre-order, post-order, in-order, and level-order.
See today's lecture video for all the juicy details!