COSC 160: Data Structures

Homework 3
Fall 2021

Due: F 9/24 @ 11:59 PM

You must upload a PDF document to Canvas. Feel free to use pencil and paper to do this homework. If you do, please do not submit a PDF document containing high-resolution digital photographs. Use a PDF scanner such as GeniusScan to produce black-and-white scans for a PDF document.

1. Insert the following keys into a binary search tree: e, h, m, k, l, p, d, f, o, s, q, r. Draw the tree after each insertion.
2. Write the keys using a pre-order traversal.
3. Write the keys using an in-order traversal.
4. Write the keys using an post-order traversal.
5. Write the keys using a level-order traversal.
6. What is the height of the tree?
7. What is the depth of m?
8. How many descendants does m have? Which keys are they?
9. How many ancestors does m have? Which keys are they?
10. List keys in the leaf nodes.
11. List keys in the internal nodes.
12. Write the path from e to l.
13. Remove the following key from the binary search tree: m, h, q, r, f, e. Draw the tree after each removal.

Copyright © 2020 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.