Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

Agenda

• Announcements
  • Remember: no class meeting Monday
  • Next Wednesday: lab practical exam, more info on class home page
  • Lab 9: Best Of continues
• Lab 7: More Linked Lists additional recap
• Lecture 26 assignment recap
• Binary Trees
  • constructing a binary tree
  • tree traversals

Lecture 28 Assignment

Due at the start of class, Friday, November 18.

Please submit answers to these questions in Blackboard under "Lecture 28 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". We have not yet studied binary search trees in detail but the idea is simple: each node in the tree has values only less than or equal to its value on the left subtree and only values greater than equal to its value on the right subtree.

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? (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)

Terminology

• tree traversals
• preorder traversal
• in-order traversal
• postorder traversal
• level-order traversal

Examples

• BinaryExpressionTree
• BTTraversals