BSC 125 - Data Structures

Problem Sets
Copyright © 2025
 Contents

1 Python Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4 Stack and Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 Recursion and Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

6 BST and AVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

 1. Python Review

Problem 1.1
Write a short Python function, is_multiple(n, m) , that takes two integer values and returns
True if n is a multiple of m , that is, n = mi for some integer i , and False otherwise

Problem 1.2
Write a short Python function, is_even(k) , that takes an integer value and returns True if k is
even, and False otherwise. However, your function cannot use the multiplication, modulo, or
division operators.

Problem 1.3
Write a Python program that repeatedly reads lines from standard input until an EOFError is
raised, and then outputs those lines in reverse order (a user can indicate end of input by typing
ctrl-D)

Problem 1.4
Write a Python class, Flower , that has three instance variables of type str, int, and float, that
respectively represent the name of the flower, its number of petals, and its price. Your class must
include a constructor method that initializes each variable to an appropriate value, and your class
should include methods for setting the value of each type, and retrieving the value of each type.

Problem 1.5
Write a method def rearrange(A, n): that takes as input a list A of size n and rearranges its
elements so that all negative numbers precede all positive numbers (do not allocate a new list).
 2. Performance Analysis

Problem 2.1

1. Show that 5n2 + 2n + 1 is O(n2 )

2. What is the Big oh of n2 + n log(n)? prove your answer.
3. Show that 2n3 ∈ / O(n2 ).
4. Assume that the expression below gives the processing time f (n) spent by an algorithm
for solving a problem of size n.

10n + 0.1n2

(a) Select the dominant term(s) having the steepest increase in n.

(b) Specify the lowest Big-Oh complexity of the algorithm.
5. Determine whether each statement is true or false and correct the expression in the latter
case:
(a) 100n3 + 8n2 + 5n is O(n4 ).
(b) 100n3 + 8n2 + 5n is O(n2 log n).

Problem 2.2

1. Find the simplest g (n), c and n0 for the following f (n) s.t: f (n) ≤ cg (n) , ∀n ≥ n0 .
(a) 6n2 + n − 4.
(b) 4 log (n) + 2.
(c) 3n3 − 20n2 + 10 log (n).
2. Find the big Oh
 notation
 for the following functions:
n3 2
(a) n + log n + n log (n).
(b) 2log(n!)+2 + 3n .

Problem 2.3

1. Order the following functions by asymptotic growth rate: 4n log n + 2n, 210 , 2log n , 3n +
100 log n, 4n, 2n , n2 + 10n, n3 , n log n.
8 Chapter 2. Performance Analysis

2. Show that log n2n + n2 is O(n2 )

3. Show that ∑5i=1 i3 is O(1)
4. Show that ∑ni=1 ⌈log i⌉ is a O(n log n)
5. Using the definition of the Big-Oh, prove that f (n) = 10n + 5 log n is a big-oh of g(n) = n.

Problem 2.4
Compute the following:
1. ∑n−1
i=0 1.
2. ∑n−1
i=i i.
3. ∑n−2
i=2 1.
4. ∑n−1 n−1
i=0 ∑ j=0 1.
n−1 n−1
5. ∑i=0 ∑ j=i 1.
6. ∑n−1 n−1
i=0 ∑ j=i+1 1.
7. ∑n−1 n
i=1 ∑ j=i 1.
j
8. ∑ni=1 ∑nj=1 ∑k=0 1.

Problem 2.5
Analyze the following code excerpts:
1.
sum_value = 0
for i in range (n , 0 , -2):
sum_value += i

2.
sum_value = 0

i = 1
while i < n :
sum_value += i
i *= 2

3.
int sum = 0;
for ( int i = 1; i <= n ; i ++)
for ( int j = 0; j < 2 * i ; j ++)
sum += j ;
return sum ;

4.
for i in range ( n * n * n ):
print ( i )
for j in range (2 , n ):
print ( j )

print ( " End ! " )

5.
int k = 100 , sum = 0;
for ( int i = 0; i < n ; i ++)
for ( j = 1; j <= k ; j ++) {
sum = i + j ;
System . out . println ( sum );
}

6.
int sum = 0;
for ( int i = 0; i < n * n ; i ++) {
for ( int j = n - 1; j >= n - 1 - i ; j - -) {
 9

sum = i + j ;
System . out . println ( sum );
}
}

7.
int sum = 0;
for ( int i = 1; i <= 2^ n ; i = i * 2) {
for ( int j = 0; j <= log ( i ); j ++) {
sum = i + j ;
System . out . println ( sum );
}
}

8.
sum_value = 0
k = 2**3
i = k
while i <= 2**( n - k ):
j = 2**( i - k )
while j < 2**( i + k ):
sum_value = i + j
print ( sum_value )
j *= 2
i *= 2

9.
int sum = 0;
for ( int i = 2^ n ; i >= 1; i = i / 2) {
for ( int j = i ; j >= 1; j = j / 2) {
sum = i + j ;
System . out . println ( sum );
}
}

10.
sum_value = 0
for i in range (n , 0 , -1):
for j in range (i , n + 1):
sum_value = i + j
print ( sum_value )

11.
int sum = 0;
for ( int i = 0; i < n ; i ++) {
for ( int j = 0; j < i ; j ++) {
for ( int k = n ; k > 0; k - -)
sum = i + j + k ;
}
}

12.
int k = 1;
for ( int i = 1; k <= n ; i *= ++ k ) {
for ( int j = 0; j < n ; j ++)
sum = i + j ;
}

13.
int sum = 0;
for ( int i = 0; i < n ; i ++) {
for ( int j = i + 1; j < n ; j ++)
sum = sum + A [ j ];
A [ i ] = A [ i ] + sum ;
}
10 Chapter 2. Performance Analysis

14.
k = 3
sum_value = 0
for i in range ( n ):
for j in range (1 , k + 1):
sum_value = i + j
print ( sum_value )

15.
for ( int i = 0; i < n * n * n ; i ++) {
System . out . println ( i );
for ( int j = 2; j < n ; j ++) {
System . out . println ( j );
}
}
System . out . println ( " Goodbye ! " );

16.
for i in range ( n * n ):
print ( i )
for j in range (4 , n + 1): # j starts from 4 and goes up to n
print ( j )

print ( " Goodbye ! " )

17.
m = 1;
while ( m < 100 ) {
system . out . println ( m );
i = 0;
while ( i < n ) {
system . out . println ( n * m );
i ++;
}
m ++;
}

18.
for ( int i = 0; i < 2 * n ; i = i + 2) {
for ( int j = 0; j < n ; j ++)
if ( j % 2 == 0)
system . out . println ( j );
}

19.
for ( int i = 0; i < n * log ( n ); i ++) {
System . out . println ( i );
for ( int j = 2; j < n ; j ++) {
System . out . println ( j );
}
}

20.
for ( int i = 0; i < n * n ; i ++) {
System . out . println ( i );
for ( int j = 2 * n ; j > n ; j - -) {
System . out . println ( j );
}
}

21.
m = 1
while m <= n :
print ( m )
i = n
 11

while i > 0:
print ( i )
i //= 2
m += 1

22.
for i in range (0 , 2 * n , 2):
for j in range ( i ):
if j % 2 == 0:
print ( j )

Problem 2.6

1. Given an n-element array X, Algorithm B chooses log n elements in X at random and

executes an O(n)-time calculation for each. What is the worst-case running time of
Algorithm B?
2. Given an n-element array X of integers, Algorithm C executes an O(n)-time computation
for each even number in X, and an O(log n)-time computation for each odd number in X.
What are the best-case and worst-case running times of Algorithm C?

Problem 2.7
Give in asymptotic notation the running time for the following algorithms:
1. Vector-vector addition (the vectors are of size n).
2. Dot product of two vectors (the vectors are of size n).
3. Matrix-vector multiplication (the matrix is of size m × n, the vector is of size n).
4. Matrix addition (the two matrices are of size m × n).
5. Matrix-Matrix multiplication (the two matrices are of size m × k and k × n respectively).

Problem 2.8
For the following functions:
1. Give two example inputs leading to the best and worst running time respectively.
2. Analyze the performance of the function in each case (best and worst).
public int func1 ( int A [] , int n ) {
int maxr = 0;
int maxi = 0;
int i = 0;
while ( i < n ) {
int j = i +1;
int nbr = 1;
while (( j < n ) && ( A [ i ] == A [ j ])) {
nbr ++;
j ++;
}
if ( nbr > maxr ) {
maxr = nbr ;
maxi = i ;
}
i= j;
}
return maxi ;
}

public int func2 ( int A [] , int n ) {

12 Chapter 2. Performance Analysis

int maxr = 0;
int maxi = 0;
int i = 0;
while ( i < n ) {
int j = i +1;
int nbr = 1;
while ( j < n ) {
if ( A [ i ] == A [ j ])
nbr ++;
j ++;
}
if ( nbr > maxr ) {
maxr = nbr ;
maxi = i ;
}
i ++;
}
return maxi ;
}

public void func3 ( int A [] , int n ) {

int i = 0;
int j = n -1;
while ( i < j ) {
while (( A [ i ] <= 0) && (i < j )) {
i ++;
}
while (( A [ j ] > 0) && (i < j )) {
j - -;
}
int tmp = A [ i ];
A [ i ]= A [ j ];
A [ j ]= tmp ;
}
}

def func4 (A , B , C ):
i = 0
j = 0
k = 0
n = len ( A )
while i < n and j < n :
if A [ i ] <= B [ j ]:
C[k] = A[i]
k += 1
i += 1
else :
C[k] = B[j]
k += 1
j += 1

if i == n :
while j < n :
C[k] = B[j]
k += 1
j += 1
else :
while i < n :
C[k] = A[i]
k += 1
 13

i += 1

Problem 2.9
The space performance (or complexity) of an algorithm is the maximum amount of memory (in
bytes) used at any point of the algorithm ignoring the input size.
■ Example 2.1 The function sum1 below uses two variables ( sum and i ) in addition to the
input A, so it is O(1) in space (and O(n) in time).
int sum1 ( int [] A , int n ) {
int sum = 0;
for ( int i = 0; i < n ; i ++) {
sum += A [ i ];
}
return sum ;
}

On the other hand, the function sum2 is O(n) in space (why?):

int sum2 ( int [] A , int n ) {
int sum = 0;
for ( int i = 0; i < n ; i ++) {
int [] B = new int [ i + 1];
for ( int j = i ; j <= i ; j ++) {
B [ j ] = A [ j ] - A [ i ];
}
for ( int j = i ; j <= i ; j ++) {
sum += B [ j ];
}
}
return sum ;
}

What is the space complexity of the following function? Justify your answer.
public void func3 ( int A [] , int n ) {
int i = 0;
int j = n -1;
while ( i < j ) {
while (( A [ i ] <= 0) && (i < j )) {
i ++;
}
while (( A [ j ] > 0) && (i < j )) {
j - -;
}
int tmp = A [ i ];
A [ i ]= A [ j ];
A [ j ]= tmp ;
}
}

Problem 2.10
The class Sort below implements three sorting algorithms: selection sort, bubble sort and
Quicksort.
import java . util . Arrays ;
14 Chapter 2. Performance Analysis

public class Sort {

public static void selectionSort ( double [] A , int n ) {
for ( int i = 0; i < n - 1; i ++) {
int min = i ;
for ( int j = i + 1; j < n ; j ++) {
if ( A [ j ] < A [ min ])
min = j ;
}
double tmp = A [ i ];
A [ i ] = A [ min ];
A [ min ] = tmp ;
}
}

public static void bubbleSort ( double A [] , int n ) {

for ( int i = 0; i < n - 1; i ++) {
for ( int j = 0; j < n - 1 - i ; j ++) {
if ( A [ j ] < A [ j + 1]) {
double tmp = A [ j ];
A [ j ] = A [ j + 1];
A [ j + 1] = tmp ;
}
}
}
}

public static void quickSort ( double A [] , int n ) {

Arrays . sort (A , 0 , n - 1);
}
}

Conduct an experimental analysis of these three algorithms as follows:

• Use arrays of sizes ranging from 10000 to 50000 with step size 10000 (so in total you
have 5 different sizes).
• Give the same input to all three algorithms.
• Fill the array with random numbers (use import random).
• For each input repeat the execution 100 times, measure the execution in nanoseconds (use
import time), and report the average time in milliseconds.
1. Write the code used for the experimental analysis.
2. Report the results as a table and as a graph.
3. Which of the three algorithms is the fastest?
4. Which of selection sort and bubble sort is faster? Which one has a larger growth rate?

Problem 2.11
Use the definition to show that:
1. loga (n) ∈ O (logb (n)) , ∀a, b > 1. (Changing the base of the logarithm does not change
the growth rate)
2. an ∈/ O (bn ) , ∀a > b > 0. (Changing the base of the exponential does change the growth
rate)

Problem 2.12

1. Find the best asymptotic notation for the following functions:

 15
 2
(a) log nn + n2 log nlog n + n2 .

(b) 2n + 2log(n!)+log n .
2. Show the following:
(a) ∑ni=1 i2 is O(n3 ).
(b) ∑n−1
k=0 log(n − k) is O(n log n).
log n−1
(c) ∑i=0 2i (log n − i) is O(n).

Problem 2.13
Use the definition to show that:
1. ∀c ∈ R, c f ∈ O( f ).
2. If ∃n0 ≥ 0, such that f (n) ≤ g(n), ∀n ≥ n0 , then f + g ∈ O(g).
3. If f ∈ O(g) and g ∈ O(h), then f ∈ O(h).

Problem 2.14
Show that:

0 =⇒ f ∈ O (g) and g ∈
/ O( f );
f (n) 
lim = c>0 =⇒ f ∈ O (g) and g ∈ O( f );
n→∞ g (n)
=⇒ f ∈
/ O (g) and g ∈ O( f ).

∞
 3. List

R Stars indicate difficulty level.

Problem 3.1

1. Write the method @staticmethod def clear(l): which removes all the elements of l.
What would you need to change if the list l were of type LinkedList ?
2. Write method insertAll as user of ADT List that takes two lists l1 , l2 and index i
and insert all elements in l2 in l1 after position i . The list l2 must not be changed.
The first element has position 0, and assume that i is a valid position.
■ Example 3.1 If l1 : A, B,C, D, and l2 : X, Z, then after calling insertList(l1, l2, 1) ,

then l1 : A, B, X, Z,C, D. ■

3. Write the method: @staticmethod def commonE(l1, l2, cl) , user of the ADT List, which
inserts the common elements between list l1 and list l2 in the list cl. Assume that the
elements in l1 and l2 are unique and the List cl is initially empty.
■ Example 3.2 If l1 : A, B,C, F, M, D, and l2 : R, M,W, F, calling commonE(l1, l2, cl)
results in cl : F, M ■

4. Write the method moveToEnd , user of the ADT List . The method takes a list l and an
index i . It will move the element at the i -th position to the end of the list. You can
assume i to be within the list, and that the first element has the position 0. Do not use
any auxiliary data structures.
■ Example 3.3 If l : a → c → d → b → r → x, then after calling moveToEnd(l, 2) , l
will be: a → c → b → r → x → d. ■

5. ⋆ Write a static method @staticmethod def mfe(l) (user of ADT) that takes as input
a non-empty list l and returns the most frequent element in the list l . If two or more
elements appear the same number of times, then the earliest one to appear in the list should
be the most frequent one.
■ Example 3.4 Assuming l : 1, 2, 3, 4, 2, 5, 3. Calling mfe(l) will return: 2. ■
18 Chapter 3. List

Problem 3.2

1. Write the method filter , member of the class LinkedList that takes as parameter an
object that implements the interface Condition below. The method removes all the
elements of the list for which the method test returns false .
public interface Condition <T > {
boolean test ( T data );
}

2. Write the method traverse , member of the class LinkedList that takes as parameter an
object that implements the interface Processor below. The methods traverses the list and
call the method process on all elements of the list.
public interface Processor <T > {
void process ( T data );
}

3. Write the method removeBetween , member of the class LinkedList . The method takes
two elements e1 and e2 , and removes all the elements between the two elements ( e1
and e2 not included). If e1 or e2 or both do not exist, no element will be removed.
You can assume the elements of the list to be unique, and that e1 ̸= e2 . Do not call any
methods and do not use any auxiliary data structures.
■ Example 3.5 If the list: a → c → d → b → r → x, then after calling removeBetween(’’c’’, ’’r’’) ,
the list becomes: a → c → r → x. ■

4. As a member of the class LinkedList , write the method insertBefore(T e, int i) that
inserts the element e before the ith element. The numbering starts from 0. Assume that
i is a valid index. Do not call any methods of the class LinkedList . Do not use any
auxiliary data structures.
■ Example 3.6 If l : A → B → C → D → E, then calling [Link](’N’, 4) changes
the list to l : A → B → C → D → N → E. Calling [Link](’N’, 0) , changes the list to
l : N → A → B → C → D → E. ■

5. Implement the following methods in the class LinkedList :

(a) Procedure insertBeforeCurrent(T e). Requires: The list l should not be full. Results:
The new element e is inserted before the current and the new element is made the
current.
(b) Procedure removeIth( i ). Requires: The list l should not be empty. Results: The
element e at position i is removed from the list (numbering starts with 0), If the
resulting list is empty current is set to NULL. If successor of the deleted element
exists it is made the new current element otherwise first element is made the new
current element.
6. Write the method removeOddElems , member of the class LinkedList , that removes all the
elements having an odd position (the position of the first element is 0). Do not call any
methods and do not use any auxiliary data structure.
■ Example 3.7 If l : A → B → C → D → E, then [Link]() returns: A → C → E. ■

7. ⋆ Write the method removeFirst , member of class LinkedList , that removes the first
occurrence of every element that appears more than once in the list. Do not use any
auxiliary data structures and do not call any methods.
■ Example 3.8 If the list contains: B → A → A → R → C → A → C → R, then after
calling removeFirst , its content becomes B → A → A → C → R. ■
 19

Problem 3.3

1. Consider the function f below, member of DoubleLinkedList :

def f ( self , n ):

p = self . head

for _ in range ( n ):
if p . next is not None :
p = p . next

if p is not None and p . next is not None :

q = p

while q . next is not None :

q = q . next

q . previous . next = None

q . previous = None
q . next = p . next
p . next = q
q . previous = p
self . head = q

Give the content of the list after each of the following cases:
(a) The list l : A, B,C, D, E, after calling l.f(1) .
(b) The list l : A, B,C, D, E, after calling l.f(0) .
(c) The list l : A, B,C, D, E, after calling l.f(2) .
(d) The list l : A, B,C, D, E, after calling l.f(5) .

Problem 3.4

1. Write the method removeEvenElems , member of the class ArrayList , that removes all the
elements having an even position (the position of the first element is 0). The method must
run in O(n). Do not call any methods and do not use any auxiliary data structure.
■ Example 3.9 If l : A, B,C, D, E, then after calling the method [Link]() l
becomes: B, D. ■

2. Write the method duplicate , member of the class ArrayList , that duplicates each ele-
ment of the list putting the duplicate right after the original. The method must run in O(n).
Do not call any methods and do not use any auxiliary data structure.
■ Example 3.10 If l : A, A, B,C, B, then after the call [Link]() , l becomes: A, A, A, A,
B, B,C,C, B, B. ■

Problem 3.5

1. Write the method checkListEndsSymmetry that receives a double linked list and an integer
number k . The method checks if the double linked list has identical k elements going
forward from the first element and backwards from the last one. The method returns true
if they are identical, and false otherwise.
■ Example 3.11 If dl = A ↔ B ↔ C ↔ D ↔ B ↔ A and k = 2, then the method should
return true . If k = 3, it should return false , since C does not equal D.
20 Chapter 3. List

2. ⋆ Write the method bubbleSort that sorts a double linked list of integers given as
input using bubble sort.

Problem 3.6
A double linked list with sentinel nodes has special header and trailer nodes that do not store
data (see Figure 3.1). Therefore, all nodes that store data have previous and next nodes, which
eliminates special cases from insert and remove.
Tail
null
Head
Current

Figure 3.1: A double linked list with sentinel nodes

Write down the code for this implementation (class DLLSentinel ).

Problem 3.7
A circular list is a list with no first or last element and where the current advances in a circular
way through the data.
1. Give a clear specification of the ADT CircularList (use the same format seen in lecture).
2. Write down the interface CircularList .
3. Write the method def print_circular_list(l: ’CircularList’): , which prints the con-
tent of l starting from the current element. At the end of the method, current must return
to its initial position.
4. Give a linked implementation of the interface CircularList (class LinkedCircularList ).
 4. Stack and Queue

Problem 4.1

1. Write the method def is_reverse(l: DoubleLinkedList[T], q: Queue[T])-> bool: that

accepts a double-linked list l and a queue q . The method should return True if and
only if the elements of l are in the reverse order of the elements of q . Use the method
__eq__ for checking equality. In python, __eq__ is a special method (also called a
"dunder" method) used to define equality comparison between objects. The content of l
and q must not change after the call.
2. Write the method is_reverse , but this time as a member of the class ArrayQueue which
accepts a list l (not a double linked list) to compare against (Do not call any method
of the class ArrayQueue ). The content of l and the queue must not change after the call.
The method signature is: def is_reverse(self, l: List[T])-> bool: .
3. Write the method def is_reverse(q1: Queue[T], q2: Queue[T])-> bool: , that checks if
q2 is the reverse of q1 .
4. Write the method def exchange(q1: Queue[T], q2: Queue[T])-> None: that exchanges
the content of the two queues without using any auxiliary data structures.
5. Write the method concat that takes as input a queue of lists and concatenates them into
a single list. The queue and the lists must not be changed after the call. The method
signature is def concat(l: Queue[List[T]])-> List[T]: .
6. Write the method concat that takes as input a queue of queues and concatenates them
into a single queue. All queues must not be changed after the call. The method signature
is def concat(q: Queue[Queue[T]])-> Queue[T]: .
7. Given a Queue q , we would like to search the queue for an element e and delete it
while keeping the order of elements intact. Do not use any auxiliary data structures. Write
the method def remove_element(q: Queue[T], e: T)-> None: . For example, if we have a
queue 10 → 8 → 6 → 7 → 2 and want to delete 7, it will be 10 → 8 → 6 → 2.
8. Write the method def remove(q: Queue[T], pos: List[int], k: int)-> None: , which re-
moves all the elements of q located at the positions indicated in pos (k is the size of pos).
Assume that pos is sorted in increasing order with no duplicates and contains only valid
positions. The numbering of the positions starts from 0 at the head. The method must run
in O(n), where n is the size of q (not O(kn)).
22 Chapter 4. Stack and Queue

■ Example 4.1 If q : A, B,C, D, E, F, G, H and pos : 1, 2, 5, then after calling remove(q, pos, 3) ,
q becomes A, D, E, G, H. ■

9. Write a static method (User of ADT) named exchange that accepts a queue q and two
integers i and j, and exchanges the elements at positions i and j (the first element in
the queue has position 0). The queue order should not change otherwise. Assume that
0 ≤ i < j < n, where n is the length of the queue.
10. Write the method intersect , user of Queue ADT, that accepts two queues q1 and q2 ,
and returns the intersection of the two queues as a new queue. There shouldn’t be any
duplicate elements in the new queue. The elements in the returned queue must have the
same order as in q1 . The inputs q1 and q2 must not change after the method. The method
signature is: def intersect(q1: Queue[T], q2: Queue[T])-> Queue[T]: .
■ Example 4.2

q1 : B → A → C → D → E → G
q2 : G → U → D → P → C
Returned queue : C → D → G

11. Write the method def swap_adj(q: Queue[T])-> None: which swaps adjacent elements in
the queue starting from the first element. Do not use any extra data structures.
■ Example 4.3 If q : A, B,C, D, E, then after calling the method swap_adj(q) , q becomes
B, A, D,C, E. ■

12. Write the method def first_eq_last(q: Queue[T])-> bool: , which returns True if the
first and last elements are equal, and False if they are not equal. The queue q must not
change after the call. Do not use any other data structure. Assume the queue q is not
empty.
■Example 4.4 If q contains: A, B,C, A, E the method will return False. If q contains:
A, B,C, F, A the method will return True. ■

13. Write the method sym_diff , user of Queue ADT, that accepts two queues q1 and q2 , and
returns the symmetric difference of the two queues as a new queue (the set of elements
that are in q1 or q2 but not in their intersection). There shouldn’t be any duplicate
elements in the new queue. In the returned queue, all the elements belonging to q1
appear in their respective order before all elements belonging to q2 also in their respective
order. The inputs q1 and q2 must not change after the method. The method signature is:
def sym_diff(q1: Queue[T], q2: Queue[T])-> Queue[T]: .

■ Example 4.5

q1 : B → A → C → D → E → G
q2 : G → U → D → P → C
Returned queue : B → A → E → U → P

Problem 4.2

1. Write the method def reverse(self)-> None: , a member of the class LinkedQueue , which
reverses the content of the queue.
 23

2. Write the method def reverse(self)-> None: , a member of the class ArrayQueue , which
reverses the content of the queue.
3. Write the method def remove(self, k: int)-> None: , a member of the class LinkedQueue ,
that removes the first k elements (assume that k has a valid value). Your method must run
in O(k).
4. Write the method def remove(self, k: int)-> None: , a member of the class ArrayQueue ,
that removes the first k elements (assume that k has a valid value). Your method must run
in O(1).
5. Rewrite the method described in Problem 4.1.9 as a member of the class LinkedQueue
and also as a member of the class ArrayQueue . Give the big-O notation for each of the
previous three methods. Which one is the fastest?
6. Write the method def swap_with_first(self, i: int)-> None: , a member of ArrayQueue ,
that takes an integer i and swaps the element at position i with the first element in its
corresponding half of the queue. If i is in the first half, it will swap with the head. If it is
in the second half, it will swap with the first element of that half. Assume the queue starts
at position 0, and 0 ≤ i < n. Assume the number of elements in the queue is even. Do not
use any auxiliary data structures.
7. Suppose you are given the values of head , tail , and max_size , members of ArrayQueue .
Compute the size of the queue.

Problem 4.3

1. Write the method def can_be_inserted(q1: PQueue[T], q2: PQueue[T])-> bool: that ac-
cepts two priority queues, q1 , q2 , and checks whether we can insert all the elements of q2
between any two elements in the first priority queue q1 . The method either returns True
if the operation is possible or False if it is not. Notice that the method only performs a
check; neither q1 nor q2 are actually changed.
2. Using the two previous methods, write the method def remove_lowest(q: LinkedPQ[T])-> None: ,
a user of the ADT, that removes all the elements having the lowest priority.
■ Example 4.6 If the queue q contains 2 → 3 → 5 → 7 → 7 → 9 → 9 → 9, then, after the
call to remove_lowest(q) , the queue becomes 2 → 3 → 5 → 7 → 7. ■

3. Write the method def change_priority(pq: PQueue[T])-> None: , a user of the ADT PQueue ,
that changes the priority of the elements with the highest priority (with the biggest number)
to the lowest priority (with the smallest number).
■ Example 4.7 If pq: (C, 7) → (B, 7) → (A, 7) → (G, 6) → (F, 4) → (D, 1), then after
calling change_priority(pq) , pq becomes: (G, 6) → (F, 4) → (D, 1) → (C, 1) → (B, 1) →
(A, 1). ■

Problem 4.4

1. Write the method def merge_pq(self, q: LinkedPQ[T])-> None: , a member of the class
LinkedPQ , that merges the priority queue q with the current one (keeping q unchanged).
The method must have a linear performance.
2. Write the method def remove_pr(self, pr: int)-> None: , a member of the class LinkedPQ
(linked priority queue) that removes all the elements having the priority pr. Do not call
any other methods and do not use any auxiliary data structure.
■ Example 4.8 If the queue contains 2 → 3 → 5 → 7 → 7 → 9 → 9 → 9, then, after the
24 Chapter 4. Stack and Queue

call to remove_pr(7) , the queue becomes 2 → 3 → 5 → 9 → 9 → 9. ■

3. Write the method def lowest_pr(self)-> int: , a member of the class LinkedPQ (linked
priority queue) that returns the lowest priority in the queue. Do not call any other methods
and do not use any auxiliary data structure.
■ Example 4.9 If the queue contains 2 → 3 → 5 → 7 → 7 → 9 → 9 → 9, then, the call to
lowest_pr() returns 9. ■

Problem 4.5

1. Suppose you want to check parentheses balance for expressions that contain a single type
of parentheses. Would you need a stack for this task? Write a pseudo-code solution for
this problem.
2. Trace the execution of the evaluation of the following expression: 2 9 3 1 + * 5 4 3 % 1 - -
+ > 35 14 8 + = ||. Show the content of the data structure(s) after parsing each operation.

+ * % - -

+ > + = ||

3. Trace the execution of the evaluation of the following expression: 4 + (9 -(3 * 2)) % 3 +
5 * (2 +(6 / 3)) -1. Draw the content of the data structure(s) after parsing each operation.
 25

+ - * % +

* + / - $

4. Trace the execution of the conversion of the following expression into infix notation: 2 9
3 1 + * 5 4 3 % 1 - - + > 35 14 8 + = ||. Show the content of the data structure(s) after
parsing each operation.

+ * % - -

+ > + = ||

5. Trace the execution of the conversion of the following expression: 4 + (9 -(3 * 2)) % 3
+ 5 * (2 +(6 / 3)) -1 into postfix notation. Draw the content of the data structure(s) after
parsing each operation.
26 Chapter 4. Stack and Queue

+ - * % +

* + / - $

Problem 4.6

1. Write the static method def concat(st1: Stack[T], st2: Stack[T])-> Stack[T] (user of
the ADT stack) that takes as input two stacks st1 , st2 and returns their concatenation as a
new stack (the two stacks st1 and st2 must not change).
■ Example 4.10 This is an example:

D
A E
D
B A
E
C B
C
st1 st2 returned stack

2. Write the method push_back (user of the Stack ADT), that takes a stack st and an integer
p , and pushes the top of the stack to the pth position. The top element in the stack is
in position 1. Assume that 1 ≤ p ≤ n, where n is the length of st . The method signature
is def pushBack(st: Stack[T], p: int)-> None .
■ Example 4.11 Assuming the stack st (from top to bottom): 1, 2, 5, 3, 10, 6. Calling
[Link](st, 4) will result in st : 2, 5, 3, 1, 10, 6. ■

3. As a user of the ADT Stack, write the following method that checks if the top element of a
stack of Integers is equal to the total sum of all lower elements in the stack. It returns true
if they are equal and false otherwise. The stack should not be changed after you call the
method. The method signature is def check_total_top(st: Stack[int])-> bool .
4. Write the static method moveAfter (user of the Stack ADT), that takes as input two stacks
st1 , st2 and an index i. It moves the elements of stack st2 after the element at position i in
 27

stack st1 . Assume that i is within the range of stack st1 , and that the top element has an
index 0. The signature is def moveAfter(st1: Stack[T], st2: Stack[T], i: int)-> None .
■ Example 4.12 If st1 (top to bottom): 5, 2, 4, 1 and st2 (top to bottom): 8, 9. After
calling moveAfter(st1, st2, 1) , st1 will be (top to bottom): 5, 2, 8, 9, 4, 1. ■

5. Write the static method countEquals (user of the Stack ADT), that takes as input a
stack st, and an element e. It returns the number of elements of stack st matching
e. The stack st should not change after calling the method. The method signature is
def countEquals(st: Stack[T], e: T)-> int .

■ Example 4.13 If st (top to bottom): 5, 2, 4, 1, 4, 2, 4. Then countEquals(st, 4) returns

3, countEquals(st, 2) returns 2, and countEquals(st, 7) returns 0. ■

6. Write the static method def removeLast(st: Stack[T])-> None (user of Stack ADT) that
takes a stack st as input, and removes the bottom element of st.
■ Example 4.14 Assuming st (top-to-bottom): 5, 7, 5, 3, 2. After calling removeLast(st)
st will be: 5, 7, 5, 3. ■

7. Write the method def topEqualsBottom(st: Stack[T])-> bool that checks if the top ele-
ment of the stack is equal to bottom element. Return true is that is the case. The stack st
should not change after the method has been called.
8. Write the method pullUpBottom , user of the ADT Stack, that moves the element in the
bottom of the stack to the top without changing the order of the other elements. The
method signature is: def pullUpBottom(st: Stack[T])-> None .
■ Example 4.15 If st (top to bottom): A → B → E → C, after calling pullUpBottom(st) ,
st becomes C → A → B → E. ■

9. Write the method def replace(st: Stack[str], a: str, b: str)-> Stack[str] , which
replaces all occurrences of the char a in the stack st by the char b and returns the result
as a new stack. The stack st must not change after the call.
■ Example 4.16 If st before the call contains: ’A’, ’B’,’C’, ’A’, ’E’ (from top
to bottom), and we called: replace(st, ’A’, ’B’) , then the returned stack contains:
’B’, ’B’, ’C’, ’B’, ’E’ , and st remains unchanged. ■

10. Write the method def nbCommon(st1: Stack[T], st2: Stack[T])-> int which returns the
number of elements that appear in both stacks. Assume that elements are unique within
each stack.
■ Example 4.17 If st1 : A, B,C, D, E, F and st2 : F, B,C, J, then nbCommon(st1, st2) re-
turns 2. ■

Problem 4.7
The goal in this problem is to implement a generalization of the ADT queue called MultiQueue ,
which consists in a set of queues numbered from 0 to n − 1. The number of queues n is fixed and
specified by the user at the time of the creation of the data structure (see example below).
This data structure is used as follows:
• An element in enqueued in one of the n queues as specified by the user.
• The Serve operation chooses the queue from which the element is removed circularly
(the queue 0 is selected first after the creation of the multiqueue). If the queue in question
is empty, the next non empty queue is selected for the serve.
■ Example 4.18 This is an example of a multiqueue consisting of four queues. Notice that
28 Chapter 4. Stack and Queue

queue 1 is empty.

0 →3→5→4
1 →
2 →1→5→2
3 →2→1→3→6

Assuming that the turn now is for queue 0 to be served, the next 6 serve operations return in
order: 3, 1, 2, 5, 5, 1. After that, the multiqueue becomes:

0 →4
1 →
2 →2
3 →3→6

The following is the specification of the ADT MultiQueue. All operations are performed on
a multiqueue called mq having n queues.
• Procedure length (l: int, i: int). Requires: 0 ≤ i < n. Results: l is set to the length of the
queue i.
• Procedure full ( f lag: boolean, i: int). Requires: 0 ≤ i < n. Results: f lag is set to true if
queue i is full, to true otherwise.
• Procedure enqueue (val: T, i: int). Requires: 0 ≤ i < n and queue i is not full. Results:
val is in enqueued in queue i.
• Procedure serve (val: T). Requires: At least one queue is not empty. Results: val is set to
the element to be served.
Use the ADT queue (class LinkedQueue ) to implement the ADT MultiQueue.

Problem 4.8
Write an array implementation of the ADT PQueue. The serve method must run in O(1),
enqueue in O(n).
 5. Recursion and Binary Trees

Problem 5.1

1. Write the method reverseArray that reverses an array of n elements. The method signature
is def reverse_array(A: list[int], lo: int, hi: int)-> None: , where lo and hi are the
lowest and highest index in the array, respectively.
■ Example 5.1 Calling reverseArray([2,4,5,12,5],0,4) , will result in 5, 12, 5, 4, 2. ■

2. Write the recursive method checkDublicateElement that checks if an element k, passed as

parameter, exists at least twice in an array A of length n.
3. Write the method isItSortedEven that checks if the elements in the array’s even indices
are sorted. The array length is n. The method should return true if they are sorted, false
otherwise. Do not use any additional data structure. The signature of the method is
def is_it_sorted_even(a: list[int], n: int)-> bool:

Problem 5.2

1. Write a recursive method, member of the class LinkedList that reverses the content of the
list (Do not use any auxiliary data structure and do not call any other method when
writing this method).

R Recursive member functions are private in general, since their parameters may
depend on the internal representation of the data structure. Consequently, such
methods are initially called from a non-recursive public member method. For
example:

class LinkedList :
def __init__ ( self ):
self . head = None
def reverse ( self ) -> None :
self . head = self . _reverse ( self . head )
def _reverse ( self , node ):
.....
30 Chapter 5. Recursion and Binary Trees

Write the recursive method def remove(List[T] l, e): that deletes all the occurrences
of the element e from the list l starting from the current element and keeping all other
elements in their order.
■ Example 5.2 If l : 2 → 1 → 3 → 2 → 4 → 2, and current pointing to 3, then after calling
remove(l, 2) , l becomes 2 → 1 → 3 → 4. ■

2. Write a recursive method merge , member of the class LinkedList that takes as input
a list l2 and merges it with the current list into one list. The current list and the in-
put list must not be modified. The merge operation creates a new list by taking the
first element from current list, then the first element from l2 then the second element
from current list then the second element from l2 and so on. The method signature is
def merge(self, l2: ’LinkedList’)-> ’LinkedList’: .

■ Example 5.3 If the list l1 contains: A → B → C, and l2 contains: D → E → F → G → H,

then the result of [Link](l2) is: A → D → B → E → C → F → G → H. ■

3. Write a recursive method merge(q1 , q2 ) that merges the queues q1 and q2 into a new queue.
After the call, q1 and q2 become empty (Do not use any loops). The method signature is:
def merge(q1: Queue[T], q2: Queue[T])-> Queue[T]: .
4. Rewrite the method merge so that the two queues q1 and q2 do not change after the call
(Do not use any loops).

Problem 5.3

1. Write the recursive method def remove_ele(st: Stack[T], e: T)-> None: that deletes
all the occurrences of the element e from the stack st keeping all other elements in their
order.
2. Write the recursive method def stack_sum(st: Stack[int])-> int: that sums all the ele-
ments in the stack and returns the total result. The stack must not changed at then end of
method.
3. Write a recursive method that checks if an array A of size n is sorted in increasing order.
4. Write the recursive method isPalindrome , member of the class DoubleLinkedList that
checks if the list is a palindrome. The method signature is def is_palindrome(self)-> bool: .

Problem 5.4
In this problem, do not use any auxiliary data structures (in particular, do not use a stack).
1. Write a recursive method, eval , to evaluate a postfix expression. The expression is
represented as a String and contains the following operators: +, -, * and /. For simplicity,
assume that all the numbers are single digit and unsigned, for instance 5, or 6 but not 23,
124 or -4. An example of an input is: ”873-*4+23-*58-+”.
2. Write a recursive method, infix , to transform a postfix expression into an infix one. Use
the same assumptions as in the previous question. For simplicity, put all operation between
parentheses. For instance, the postfix expression ”23+” is transformed to ”(2+3)”, and
”873-*4+23-*58-+” is transformed to ”((((8*(7-3))+4)*(2-3))+(5-8))”.
class Postfix :
@staticmethod
def _rec_eval ( exp : str , index : int ) -> tuple [ float , int ]:
# Private recursive method

@staticmethod
 31

def eval ( exp : str ) -> float :

# Public non - recursive wrapper
# Should call _rec_eval

@staticmethod
def _rec_infix ( exp : str , index : int ) -> tuple [ str , int ]:
# Private recursive method

@staticmethod
def infix ( exp : str ) -> str :
# Public non - recursive wrapper
# Should call _rec_infix

Problem 5.5

1. Show the result of method traverse for the binary tree in Figure 5.1 where we simply print
the letters in all the nodes. Write the result for all three approaches: Inorder, Preorder and
Postorder.

B C

D E F G

H I

Figure 5.1: Binary Tree.

2. Implement all three methods (Inorder, Preorder, Postorder) for traversing the binary tree
using recursion. The traverse method has the following signature:

class TreeTraversal :
def traverse ( self , proc : NodeProcessor , order : Order ) -> None :
# Implementation goes here

where NodeProcessor is the interface:

from abc import ABC , abstractmethod
from typing import Generic , TypeVar
T = TypeVar ( ’T ’)

class NodeProcessor ( ABC , Generic [ T ]):

@abstractmethod
def process ( self , data : T ) -> bool :
pass

The traverse method visits the nodes of the tree according to the specified order and
calls the method process on the nodes’ data. The traversal terminates when all the nodes
in the tree have been visited, or when process return false. The order is specified by a
variable of type Order , which is an enumeration of tree traversal orders:
from enum import Enum
32 Chapter 5. Recursion and Binary Trees

class Order ( Enum ):

PREORDER = 1
INORDER = 2
POSTORDER = 3

Problem 5.6

1. As a user of the ADT Binary Tree, write the instructions necessary to transform the tree
shown in Figure 5.2 into the one shown in Figure 5.3 (let the tree be called bt , a variable
of type BT[str]] ).

B C

D E F G

Figure 5.2: A binary tree (H is the left child of D).

C B

G F E D

Figure 5.3: The mirror of the tree shown in Figure 5.2 (H is the right child of D).

2. Draw the tree shown in Figure 5.2 after calling the method func written below.
class BTNode [ T ]:
def __init__ ( self , data , left = None , right = None ):
self . data = data
self . left : BTNode | None = left
self . right : BTNode | None = right
 33

class LinkedBT [ T ]( BT ):
def __init__ ( self ):
self . root : BTNode | None = None

def func ( self ) -> None :

self . _rec_func ( self . root , True )

def _rec_func ( self , t : BTNode [ T ] | None , flag : bool ) -> None :

if t is None :
return

self . _rec_func ( t . left , flag )

self . _rec_func ( t . right , not flag )

if flag :
t . left , t . right = t . right , t . left

Problem 5.7
A perfect binary tree is a binary tree where all leaf nodes are at the same level. A full binary
tree is a binary tree where all leaf nodes are at the same depth.

1. Given the height h of a perfect full binary tree, How can we know the number of leaf
nodes l? Assume that the height of a single root node is 0.
2. How can we know the total number of nodes n in a perfect full binary tree if we knew the
height is h?
3. If we know the total number of nodes in a perfect full binary tree is n, how can we know
the number of non-leaf nodes?

Problem 5.8

1. Write the iterative method collectInOrder , member of the class BT (binary tree) that
returns a list that contains all the data in the tree in the InOrder order.
The method signature is: def collectInOrder(self)-> List[T]: .
■ Example 5.4 For the tree shown in Figure 5.3, the output to collectInOrder() is the
list: G → C → F → A → E → B → H → D. ■

2. Write the recursive method mirror , member of the class BT, that transforms the tree into
its mirror (see Figure 5.3 for an example). This method calls the private recursive method
recMirror .
3. Write the recursive method find , a private member method of the class BT (binary tree)
that takes as input a node t and data e and returns true if e exists in the subtree rooted at t,
false otherwise. The method signature is: def _find(self, t: BTNode[T] | None,T e)-> bool: .
34 Chapter 5. Recursion and Binary Trees

C B

E D F

Figure 5.4: A binary tree.

■ Example 5.5 In the tree shown in Figure 5.4, the call to find("E") with the node

containing data C as parameter returns true, whereas the call with the node containing data
B as parameter returns false. ■

4. Write a recursive method sizeBalanced , member of the class BT (Binary Tree), that
returns true if the tree is empty, or, at every node, the absolute value of the difference
between the number of nodes in the two subtrees of the node is at most 1. The method sig-
nature is: def sizeBalanced(self)-> int: (this method calls the private recursive method
recSizeBalanced ).

■ Example 5.6 The binary tree shown shown in Figure 5.4 is not size balanced. The size
balance at E is -1, at C is -1, at B is -1, but at A , the size balance is 2-4=-2. ■

Problem 5.9

1. Write the recursive method isMirror , member of the class BT (Binary Tree), that takes
as input a binary tree and returns true if the two trees are the mirror image of each other.
The method signature is def isMirror(self, bt:BT[T])-> bool: (this method must call
the private recursive method recIsMirror ). Important: Non-recursive solutions are not
accepted.
■ Example 5.7 The two trees shown below are mirror images of each other.

A A

B C C B

F E D D E F

G G

■
 35

2. Write the recursive method twoChildren , member of the class BT (Binary Tree), which
returns the number of nodes with two children. Do not use any auxiliary data structures
and do not call any BT methods. The method signature is def twoChildren(self)-> int: .
This method must call the private recursive method recTwoChildren . Important: Non-
recursive solutions are not accepted.

Problem 5.10

1. Write the recursive method atLevel(int l) , member of the class BT (Binary Tree), which
returns the number of nodes at level l. We consider the root of the tree to be at level
1. Assume also that l ≥ 1. The method signature is def atLevel( l:int)-> int . This
method must call the private recursive method recAtLevel . Do not use any auxiliary data
structures and do not call any BT methods.
■ Example 5.8 The call atLevel(2) on the binary tree shown below returns 2, atLevel(3)

returns 2, atLevel(1) returns 1, atLevel(6) returns 0. ■

C B

E D F

2. An arithmetic expression can be represented as a binary tree as shown in the figure below.

- +

3 / 2 5

4 2

Write the recursive method def eval(expr:BT[Token])->float that evaluates the expression
expr. The class Token represents a token of the expression and is described as follows.
from enum import Enum
class TokenType ( Enum ):
OPERAND = ’ Operand ’
36 Chapter 5. Recursion and Binary Trees

OPERATION = ’ Operation ’

class Token :
....
# Returns the type of the token
def getType ( self ) -> TokenType :

# Returns the value of the token if it is of type Operand

def getVal ( self ) -> float :

# If the token is of type Operation , this method

# applies it to the operands passed as parameters
# and returns the result of the operation .
def apply ( self , op1 : float , op2 : float ) -> float :

Assume that the tree expr is not empty.

 6. BST and AVL

Problem 6.1
Consider the binary search tree shown in Figure 6.1.
1. Draw the tree after inserting the keys: 3, 9, 7 and 4.
2. Draw the tree (obtained in Step 1 after all 4 inserts) after deleting the keys: 1, 10, 8 and 9.

4 12

2 5 10 15

Figure 6.1: A binary search tree (1 is the left child of 2).

Problem 6.2

1. Write a recursive version of the method findKey , member of the class BST (see the
specification in the slides).
2. Write the method removeLarger , member of the class BST that takes as input a key k that
exists in the tree and removes all the keys that are (strictly) larger than k.
3. Write the method nbLess , member of the class BST that takes as input a key k and returns
the number of keys in the tree that are smaller or equal k.

Problem 6.3
38 Chapter 6. BST and AVL

1. List the keys (not the data) of the tree shown in Figure 6.3 in reverse inorder (right, node,
left). What do you notice?
2. Write the method kLargest , member of the class BST that takes as input an integer k and
returns a queue that contains the data corresponding to the k largest keys in the tree. The
order of the data in the queue must be in reverse order of that of the keys. Assume that k is
less or equal the size of the tree.
■Example 6.1 For the tree shown in Figure 6.3, the output to kLargest(4) is the queue:
G → C → F → A. ■

Hint: Use the observation you made in Part 1 of this problem and combine it with the idea
of Problem 2.1.

8
A

4 12
B C

2 5 10 15
D E F G

1
H

Figure 6.2: A binary search tree (H is the left child of D). The keys are the numbers, whereas
the letters are the data.

Problem 6.4
Write the method intervalSearch , member of the class BST , that takes as input two keys k1 and
k2 and returns a queue that contains the data of all nodes that have keys in the interval [k1 , k2 ].
The order of the data in the queue must be the same as that of the keys.

■Example 6.2 For example, the call to the method intervalSearch(5,14) on the tree shown in
Figure 6.3, returns the queue that contains: E → A → C → F. ■
 39

8
A

4 12
B C

2 5 10 15
D E F G

1
H

Figure 6.3: A binary search tree (H is the left child of D). The keys are the numbers, whereas
the letters are the data.

Problem 6.5

1. As a member of the class BST, write the method def isLeftRangeLarger(BSTNode[T] t)-> bool:
that measures the range of possible values that can be found in the left subtree of t and
compares it with the range of its right subtree. The method returns true if left is larger,
false otherwise.

15

5 25

3 10 20 35

1 4

Figure 6.4: Binary Search Tree.

■ Example 6.3 For the BST in Figure 6.4, isLeftRangeLarger(root) will measure the
left range as 15-1=14 and the right range as 35-15=20 which means the method will return
false.
■

2. Write a method isSearchPathLinear(int k)-> bool: that checks if the search path of the
given key k has a linear structure or not. A linear structure means that the path from root
to the key k has either all left edges or all right edges (assume that k exists in the tree).
■ Example 6.4 For the BST in Figure 6.4, if the method receives the key 35, the method
isSearchPathLinear will return true given the path is all right edges. If the method gets
the key 10, the method will return false. ■

Problem 6.6
40 Chapter 6. BST and AVL

1. Write the method secondMin , member of the class BST , that returns the data associated
with second minimum key in the tree. Assume that the tress has at least two keys.
2. Write the method inSubtree , member of class BST , that will check if a given key
k2 is in the subtree of another given key k1 . The method should return true if k1 ex-
ists and k2 is in the subtree rooted at k1 , false otherwise. The method signature is
def inSubtree(int k1, int k2)-> bool: .

Problem 6.7

1. Write the method def swapData(int k) , member of the class BST , that swaps the data
associated with the key k with the data of its parent. If the key k does not exist or the
corresponding node has no parent, the tree is unchanged. Do not call any methods of the
class BST .
2. Write a member method that prints the keys of a BST in reverse order (note that in-order
traversal of a BST visits the nodes in increasing order, so how can we visit the largest keys
first?).

Problem 6.8

1. Write the method def nbInRange(int k1, int k2)-> int: , member of the class BST , which
returns the number of keys k in the BST that statisfy: k1 ≤ k ≤ k2 . Make sure that the
method does not visit any unncessary nodes.
2. Write the method def _deepestKey(BSTNode[T] t)-> int: , member of BST which returns
the key associated with the deepest node in the subtree t. In case of a tie (two keys at the
same depth), the smallest key should be returned. As precondition, t must not be empty.
3. Write the member method def maxKey (int k)-> int: of the class BST (binary search tree)
that returns the maximum key of the sub-tree rooted at the node with key k. Assume that k
exists.
■ Example 6.5 For the tree below, maxKey(16) returns 18, maxKey(48) returns 48.

20

16 43

11 18 35 48

10 12 45

Figure 6.5: BST example

■
 41

60

80

90

95

Figure 6.6: BST Tree.

Problem 6.9
Given the BST tree in Figure 6.6, what are the needed steps to convert this BST into an AVL
tree? In English, write the algorithmic steps needed to do the task. Draw the AVL tree after
converting the BST. Make sure to show your steps clearly including: what type of rotation is
performed (rotate left or right) and show the balance of the tree after each step.

Problem 6.10

1. Draw the following AVL trees after inserting each of the specified keys. Indicate the pivot
if it exists and the type of rotation used to balance the tree if required.

68

68

20 72

20 72
3 44 71

3 44
35 51

(a) Insert 69 (b) Insert 48

68 68

20 72 20 72

3 44 69 3 44 69

51 35 51

(c) Insert 70 (d) Insert 38

2. Draw the following AVL trees after deleting each of the specified keys. Indicate the type
of the rotation(s) used to balance the tree if required.
42 Chapter 6. BST and AVL

68

68

20 72

20 72
3 44 71

3 44
35 51

(a) Delete 72 (b) Delete 71

68

20 73

3 44 70 81

35 48 69 71 78 92

72

(c) Delete 3

Problem 6.11
Complete the table below by computing the resulting balance for each of the specified rotations
made on the trees shown in Figure 6.7.

Case Initial balance Rotation Resulting balance

(a) Bal(A)=-2, Bal(B)=-1 R(A) Bal(A)=?, Bal(B)=?
(a) Bal(A)=-2, Bal(B)=0 R(A) Bal(A)=?, Bal(B)=?
(b) Bal(A)=2, Bal(B)=1 L(A) Bal(A)=?, Bal(B)=?
(b) Bal(A)=2, Bal(B)=2 L(A) Bal(A)=?, Bal(B)=?
(c) Bal(A)=-2, Bal(B)=1, Bal(c)=-1 L(B), R(A) Bal(A)=?, Bal(B)=?, Bal(C)=?
(c) Bal(A)=-2, Bal(B)=1, Bal(c)=0 L(B), R(A) Bal(A)=?, Bal(B)=?, Bal(C)=?
(c) Bal(A)=-2, Bal(B)=2, Bal(c)=-1 L(B), R(A) Bal(A)=?, Bal(B)=?, Bal(C)=?
(d) Bal(A)=2, Bal(B)=-1, Bal(c)=0 R(B), L(A) Bal(A)=?, Bal(B)=?, Bal(C)=?
(d) Bal(A)=2, Bal(B)=-1, Bal(c)=-2 R(B), L(A) Bal(A)=?, Bal(B)=?, Bal(C)=?

■ Example 6.6 For the first line:

 43
-2 0
A
B
-1 0

B A

h-1
T3
T1

h
Right rotation

h-1

h-1
T2 T3

h-1
T1 T2
h

A A

B B
T3 T1

T1 T2 T2 T3

(a) (b)

A A
B B

C C
T4 T1
T1 T4

T2 T3 T2 T3

(c) (d)

Figure 6.7: Trees.

Problem 6.12

1. Write:
(a) The method def _rRot(AVLNodep[T] p)-> AVLNode[T]: , member of the class AVLTree
that performs a right rotation at p and returns the new root of the subtree.
(b) The method def _lRot(AVLNodep[T] p)-> AVLNode[T]: , member of the class AVLTree
that performs a left rotation at p and returns the new root of the subtree.
(c) Use the two previous methods to write the method def _rlRot(AVLNode[T] p)-> AVLNode[T]: ,
member of the class AVLTree that performs a right-left rotation at p and returns the
new root of the subtree.
2. Write the method def _height(AVLNode[T] t)-> int: , member of the class AVLTree , that
returns the height h of the subtree rooted at t (an empty subtree has height 0). The methods
must be O(h) in time.