Homework #3 CS 2420 solution

Written Assignments (40 points)
1. (10 points) Consider a tree storing 100,000 items. What is the worst-case height of T in the following cases:
a. T is an AVL tree.
b. T is a binary search tree.
Justify your answers.
2. (15 points) Write the pre-order, post-order, and breadth-first order of the following tree.
3. (15 points) Draw the final binary search tree that is constructed by the following sequence of operations:
Add(20), Add(5), Add(15), Add(30), Add(40), Add(25) Add(10), Add(12), Add(8), Add(28), Delete(20),
Programming Assignment (60 points)
An input file tree.txt contains a binary tree T for Questions 4 and 5 in the following format:
Each line represents a node, In each line, 1st field is a member ID, 2nd field is a parent ID of the member ID,
and 3rd field is the member ID's position (e.g., left, right or root). The root indicates this member ID is a root
node, so a member ID 5 is a root node in the above example, and ignore a member ID 0.
Visualized input data looks like this:
4. (30 points) Read the tree.txt file, create a binary tree based on the input file, write a function to find the depth
of a given node. Your program should support an interactive commend line interface. For example, we will type
a member ID 11 on the interactive command line interface, and your program is supposed to return (display) its
depth 2. What is the running time of the algorithm to find the depth of a given node in terms of Big-O? Save the
program in a file called findDepth.cpp. Describe your program in your answer note.
5. (30 points) Write a program that takes the input file tree.txt, and outputs the tree that results after removing
all leaves from T. Save your program as removeLeaves.cpp. Describe your program in your answer note.
All submitted source codes will be passed to Stanford MOSS (http://theory.stanford.edu/~aiken/moss/) for
detecting software plagiarism. You are NOT supposed to copy and paste online solutions nor your collegue's
What to turn in:
 Include your name and A number at the top of each file (PDF and two programming files).
 Compress the three files (i) your answer note for questions 1, 2, 3, 4 and 5 in PDF file format (ii) your
findDepth.cpp; and (iii) removeLeaves.cpp. You may include additional files (e.g., .h file) for the
questions 4 and 5.
 Name the compressed file as hw03_FIRSTNAME_LASTNAME.zip. For example, if your name is
John Smith, name the file as hw03_John_Smith.zip. Submit the compressed file to Canvas.
 Make sure all your programs are fully commented, and compile and run correctly.
 This is an individual assignment, but you may discuss general strategies and approaches with
other members of the class (refer to the syllabus for details of the homework collaboration
policy). If you discussed an assignment with your colleague, explicitly report the colleague's name and
what you discussed in your submission.
 Follow Code of Conduct (refer to the syllabus for details).