Lesson 5.3: Tree Traversals
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 5.3-traversal-203-1221.pdf Download 5.3-traversal-203-1221.pdf | PDF Download PDF |
On Zoom Cloud Recordings on Canvas |
| 1–2PM | 5.3-tree-traversals-1pm.pdf Download 5.3-tree-traversals-1pm.pdf | 5.3-tree-traversals-1pm-annotated.pdf Download 5.3-tree-traversals-1pm-annotated.pdf |
On Zoom Cloud Recordings on Canvas |
| 4–5PM | 5.3-tree-traversals-4pm.pdf Download 5.3-tree-traversals-4pm.pdf | 5.3-tree-traversals-4pm-annotated.pdf Download 5.3-tree-traversals-4pm-annotated.pdf |
On Zoom Cloud Recordings on Canvas |
Readings:
- Carrano & Henry: Chapter 15.2 (Binary trees and traversal)
Summary:
The day includes speculation on a pointer-based implementation for binary trees. In addition, we discuss recursive traversals, and analyze their running time. Finally, we learn about 2 specific applications of recursive traversal.
Learning Outcomes:
- Derive space implications of pointer-based binary tree implementation.
- Explore traversal options for navigating all of the data contained in a tree.
- Derive and justify running time for traversal.
- Explore and analyze 2 standard applications of tree traversal.