### 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.

- 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.
- Write the keys using a pre-order traversal.
- Write the keys using an in-order traversal.
- Write the keys using an post-order traversal.
- Write the keys using a level-order traversal.
- What is the height of the tree?
- What is the depth of m?
- How many descendants does m have? Which keys are they?
- How many ancestors does m have? Which keys are they?
- List keys in the leaf nodes.
- List keys in the internal nodes.
- Write the path from e to l.
- 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.
*