SUNY Geneseo Department of Computer Science

Problem Set 12 -- Trees

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Wednesday, April 11

Purpose

The goal of this exercise is to consolidate your understanding of basic tree terminology, properties, and algorithms.

Background

This exercise is based on material in Chapter 13 of our textbook. This material was covered in the lectures of April 4, April 6, and April 9.

Exercise

Answer the following questions. The questions refer to the following trees:

[2 Ordered Binary Trees]

Both are ordered binary trees; Tree A is a tree of integers, ordered by numeric order; Tree B is a tree of strings, ordered by alphabetical order.

Question 1

What is the height of Tree A? Of Tree B?

Question 2

Show the tree that would result from inserting 4 into Tree A, using the textbook's insertion algorithm. Show the tree that would result from inserting "Python" into Tree B, using the textbook's insertion algorithm.

Question 3

Show a balanced ordered binary tree containing the same elements as Tree B (ignoring the insertion from Question 2).

Question 4

Using either Tree A or Tree B, give examples of each of the following:

Question 5

Informally, a "trinary tree" is a tree in which each node has at most 3 children. Give a formal, recursive, definition of "trinary tree."

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.