1
h07
CS24 F19
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h07: Chapter 10: Trees

ready? assigned due points
true Fri 11/08 12:00AM Mon 11/18 11:59PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

INSTEAD OF TURNING IN THIS HOMEWORK, YOU WILL TAKE A QUIZ ON GAUCHOSPACE BY THE DUE DATE.
There is NO MAKEUP for missed homework assignments.
The quiz will be made available at least two days before the due date.

Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Read Chpater 10 (If you don’t have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”).

    1. (10 pts) Draw a binary search tree with 6 nodes containing the integer keys 60, 30, 40, 50, 20, 10. You can arrange these in any order as long as the resultant tree satisfies the properties of a BST. Circle the root, and put asterisks on each leaf. Find two nodes that are siblings and connect them with a wigly line.
    2. (10 pts) Look at the tree in Figure 10.5 on page 484. In what order are the letters printed for an in-order traversal? What about a post-order traversal?
    3. (10 pts) Write a function with the prototype void stars(int i);. The function prints a line of i stars followed by a new line. Write code to apply the stars function to every node in a binary tree using an in-order traversal, where the number of stars is that given by the data of the node in the BST. You must write both the function definition and the code that uses it with the star function
    4. (2 pts) Why is it bad to insert nodes from smallest to largest in a binary search tree?
    5. (5 pts) Build a binary search tree with the following words (inserted in the provided order): Kenya, Austria, Ireland, Norway, Laos, Germany, Moldova
    6. (3 pts) Search for the following keys in the BST that you created in the previous question: Ireland, Germany, Moldova and in each case indicate the nodes that you visited along the way.