Programming Question

CS210 Data Structures and Algorithms Spring 2023
Assignment #3
TOTAL POINTS: 25
Name:
1. (10 Points) Assume this tree is a Binary Search Tree even though you cannot see what
the keys and values are at the nodes (the letters we write below are just “names” for the
nodes for the purpose of answering the questions).
a. The value of G is greater than the value of I (True/False)
b. This Binary Search Tree is complete (True/False)
c. What is the height of the tree?
d. What is the maximum number of nodes that could be added to the tree without
increasing its height?
e. If Node C were to be deleted, which node would be its successor?
CS210
Spring 2023
Manju Muralidharan
2. (5 Points)
•
Describe the most time-efficient way to implement the operations listed below. Assume
no duplicate values and that you can implement the operation as a member function of
the class – with access to the underlying data structure, including knowing the number of
values currently stored (N). Pseudo code is not necessary but may be written. You can use
diagrams to support your answer.
•
Then, give the tightest possible upper bound for the worst-case running time for each
operation in terms of N.
For any credit, you must explain why it gets this worst-case running time.
Given a binary search tree, find which value is the minimum value and delete it.
CS210
Spring 2023
Manju Muralidharan
3. (5 Points) AVL Trees Draw the AVL tree that results from inserting the keys: 12, 50, 46, 28, 91, 37
in that order into an initially empty AVL tree.
Draw all Intermediate Trees.
The height factor / balance factor of each node must be mentioned for every intermediate tree.
You must also indicate which node creates the imbalance and highlight & mention each type of
rotation (LL, RR, LR, RL) for each rotation.
All the above must be done for any credit.
CS210
Spring 2023
Manju Muralidharan
4. (5 Points) From your understanding of Data structures so far, specify with justification, which
Data Structure you would use in the following scenarios.
You must mention both names and give reason for any credit.
a. Insertion and Deletion need to be performed at constant time and the size of input grows
dynamically.
b. Given an element “x”, user must find all values that are greater than x. Time taken must be
less than linear growth.
c. Insertion, Deletion and search of an element in a linked format must guarantee a
logarithmic time.
CS210
Spring 2023
Manju Muralidharan
d. Multiple processes are being executed in a nested format, outermost process executes last
and innermost executes first. The state of the outermost process must be saved till the
innermost process finishes.
e. A set of (key, value) pair records are given. Data is dumped and looked up often. Other
operations are not important. Key is not unique for values.
CS210
Spring 2023
Manju Muralidharan