## CS 2401 Assignment #9

Due Date: Monday, April 25 or Tuesday, April 26, depending on the day of your lab.

Objective: The goal of this assignment is to practice the use of heaps and array implementation of trees.

Reminder: In an array representation of a tree, for an element a[k] stored in the k-th cell, its left child is stored as a[2k+1] and its right child is stored as a[2k+2]. For example, a tree

```       3
/   \
1     5
/ \   / \
0   2 4   6
```
is stored as follows:
``` 3    1    5    0    2    4    6
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
```
In this implementation, to describe a subtree, it is sufficient to describe its root. For example, if we give the index 2 (corresponding to element 5), this describe the following subtree:
```       5
/ \
4   6
```
For simplicity, let us assume that all elements of the tree are non-negative integers, and -1 means that that there is no element. For example, a tree
```       3
/   \
1     5
\   /
2 4
```
is stored as follows:
``` 3    1    5    -1   2    4    -1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
```

Assignment: For the array representation of the trees, write several recursive methods related to trees:

• a method that, given an array and an index, returns the smallest element of the corresponding subtree;
• a method that, given an array and an index, returns the largest element of the corresponding subtree;
• a method that, given an array and an index, returns the total number of elements in the corresponding subtree;
• a method that, given an array and an index, returns the height of the corresponding subtree;
• a method that, given an element, an array, and an index, checks whether the given element belongs to the corresponding subtree;
• a method that, given an element, an array, and an index, adds the given element to the corresponding subtree.