Please give the solution in C language only and attach the output screenshot

QA 23.6 Write a program to compute the median element of the set of elements stored in the AVL tree.

The median of a set of n numbers is the element that appears in the n/2 th position, when the set

is written in sorted order. When n is even, n/2 and when n is odd, (n + 1)/2 is the position for

the median element. For example, if the set is 3, 2, 1, 4, 6 then the set in sorted order is 1, 2, 3,

4, 6, and the median is 3.

Consider a modified AVL tree in which each parent node stores both a key and the total no of nodes

in the right and left subtree + 1 .

struct node {

int key ;

int no of elements ;

struct node left;

struct node right ;

}

Heres an example of how the modified AVL tree would look (the number after a semicolon indicates the total no of elements in the right and left subtree + 1 ).

As the number of nodes below a given node does not remain the same, the no of elements value

at needs to be computed after each iteration. For example, after inserting 21 , the no of elements

values at the root node increased and updated as 8, similarly at node 18 its get decreased and

updated as 1.

Do not alter the structure of the tree (should use only one tree). Your program should include the

following functions.

getMedian(struct node* root): returns median element of the AVL tree.

Input Format:

Each line contains a character i followed by an integer separated by a space; a node with this

integer as key is created and inserted into the AVL.

Character g, is to get the median of the AVL tree.

Character t is to terminate the program.

Output Format:

Print median of the AVL tree.

Constraints:

1 <= n <= 1000

Sample Input 1:

i 17

i 11

i 29

i 8

i 18

i 31

i 25

g

t

Sample Output 1:

18

Sample Input 2:

i 37

i 21

i 80

i 81

g

t

Sample Output 2:

37