Due Friday, December 4th at 11:59 AM sharp.

Please read the preamble in Assignment 1.

In this assignment, you may use any material introduced in this course.

**Problem 0 is a "warm-up" question. You are allowed to collaborate with your fellow classmates and discuss the solution on piazza.**

Given an implementation of tree.h and tree.c, add the following declaration to tree.h and corresponding implementation to tree.c:

//Return the number of elements in t int size(struct inttree *t);This operation must have O(1) running time. Sample test:

struct inttree *t = create(); insert(t, 5); insert(t, 10); assert(size(t) == 2));

Add the following declaration to tree.h and corresponding implementation to tree.c:

//Return the maximum element in t int max(struct inttree *t);This operation must have O(1) running time. Include a comment showing that your solution meets the time constraint. Sample test:

struct inttree *t = create(); insert(t, 30); insert(t, 50); insert(t, 25); assert(max(t) == 50);

Add the following declaration to tree.h and corresponding implementation to tree.c:

//Return the sum of the elements in t that are between a and b, inclusive int sumrange(int a, int b, struct inttree *t);This operation must have O(height(t)) running time. Include a comment showing that your solution meets the time constraint. Sample test:

struct inttree *t = create(); insert(t, 30); insert(t, 50); insert(t, 25); assert(sumrange(28, 55, t) == 80);

Add the following declaration to tree.h and corresponding implementation to tree.c:

//Return the ith element of t, where i = 0 returns the smallest //elements, i = 1 returns the next smallest, and so on //Requires: i < size(t) int ith(int i, struct inttree *t);This operation must have O(height(t)) running time. Include a comment showing that your solution meets the time constraint. Sample test:

struct inttree *t = create(); insert(t, 50); insert(t, 35); insert(t, 100); assert(ith(0, t) == 35); assert(ith(1, t) == 50); assert(ith(2, t) == 100);

Add the following declaration to tree.h and corresponding implementation to tree.c:

//Deletes the element e from t, by promoting the right subtree of the subtree rooted at e, and inserting the left subtree into it. //The provided delete functions promotes the left subtree void delete_right(int e, struct inttree *t);This operation must have O(height(t)) running time. Include a comment showing that your solution meets the time constraint. Sample test:

struct inttree *t = create(); insert(t, 20); insert(t, 50); insert(t, 10); delete_right(t, 20); print(t);This test should print

50 10