Fall 2016, Siena College

Lecture 28: Binary Trees
Date: Friday, November 11, 2016

Agenda

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