Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

Agenda

• Announcements
  • Today's office hours moved to 1:30-2:30
  • Note the zyBook activities due when we get back from break listed on the last lecture page, and new things also due Monday on today's page
• Programming Project 4: P.S.: It's Just a Stack due tomorrow afternoon
• Exam 3 information
  • Practice exam 3 out
  • Tentative plan: Tuesday evening review session, 7-8:30
  • Today's topic is the cutoff for what will be covered, but the material on trees will mostly end up on the final exam
• Lecture 26 assignment recap
• Binary Search Trees
• BST implementations
• Balanced Search Trees

Lecture 29 Assignment

Due at the start of class, Monday, November 27.

Please submit answers to these questions in Blackboard under "Lecture 29 Assignment" by the start of class. We will discuss these questions at the start of class, so no late submissions can be accepted. For the first three questions, consider three-node integer-valued binary trees whose nodes contain the elements "1", "2", and "3". The last two items previously in this space will become part of a future assignment.

1. Draw all valid trees whose in-order traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? Note that there are several valid tree "shapes" in each case. (3 points)
2. Draw all valid trees whose preorder traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? (3 points)
3. Draw all valid trees whose postorder traversal would visit the nodes in the order 1-2-3. Which of these are binary search trees? (3 points)
4. Bailey Problem 12.8, p. 310. (5 points)
5. Bailey Problem 12.10, p. 311. (6 points)
6. Bailey Problem 12.20, p. 311 (5 points)

Terminology

• binary search tree
• balanced tree/balance condition
• red-black trees