CSSE 230: Session Notes - Day 5

Topics

• Staying consistent with the way a language generally handles boundary conditions.
• Tree traversal
• Tree iterators
• Lazy iterators
• Review of basic analysis of algorithms

Outline

• [5 min] Class discussion of return format of the toString method. What does Java do? Let's have a look at the documentation for ArrayLists.
• [5 min] Writing good code: Returning -1 vs. throwing an exception in height.
• [5 min] Writing good code: Testing for null children vs. try-catch in the recursive functions in the BinaryNode class. Use tests!
• [10 min] Tree traversal:
  • In-order
  • Reverse-order
  • Pre-order
  • Level-order
• [10 min] Introduction to TreeIterators. Discussion of storing the tree in the Iterator.
• [5 min] Definition of Lazy Iterators
• [10 min] Group work: How to implement a lazy Iterator.
• [5 min] Class discussion of group work.
• [5 min] Break
• [20 min] Review of basic analysis of algorithms:
  • Growth functions
  • Best, worst, average case analysis
  • What to count
• [Balance of time] Work on the BST - part 2 project.

Resources

• Tree traversal worksheet
• Basic analysis of algorithms worksheet