1#include <stdio.h>
2#include <stdlib.h>
3#include <math.h>
4
5struct TreeNode {
6    int val;
7    struct TreeNode *left;
8    struct TreeNode *right;
9};
10
11struct QueueNode {
12    struct TreeNode *node;
13    struct QueueNode *next;
14};
15
16struct Queue {
17    struct QueueNode *front, *rear;
18};
19
20struct Queue* createQueue() {
21    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
22    q->front = q->rear = NULL;
23    return q;
24}
25
26void enqueue(struct Queue* q, struct TreeNode* node) {
27    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
28    newNode->node = node;
29    newNode->next = NULL;
30    if (q->rear == NULL) {
31        q->front = q->rear = newNode;
32        return;
33    }
34    q->rear->next = newNode;
35    q->rear = newNode;
36}
37
38struct TreeNode* dequeue(struct Queue* q) {
39    if (q->front == NULL) return NULL;
40    struct QueueNode* temp = q->front;
41    q->front = q->front->next;
42    if (q->front == NULL) q->rear = NULL;
43    struct TreeNode* node = temp->node;
44    free(temp);
45    return node;
46}
47
48int isQueueEmpty(struct Queue* q) {
49    return q->front == NULL;
50}
51
52// Function to find average of nodes at each level
53void averageOfLevels(struct TreeNode* root) {
54    if (!root) return;
55    struct Queue* q = createQueue();
56    enqueue(q, root);
57    while (!isQueueEmpty(q)) {
58        int count = 0;
59        double sum = 0;
60        struct Queue* level = createQueue();
61        while (!isQueueEmpty(q)) {
62            struct TreeNode* node = dequeue(q);
63            sum += node->val;
64            count++;
65            if (node->left) enqueue(level, node->left);
66            if (node->right) enqueue(level, node->right);
67        }
68        printf("%.5f ", sum / count);
69        free(q);
70        q = level;
71    }
72}
73
74int main() {
75    /* Create Binary tree with nodes */
76    struct TreeNode a, b, c, d, e;
77    a.val = 3; a.left = &b; a.right = &c;
78    b.val = 9; b.left = NULL; b.right = NULL;
79    c.val = 20; c.left = &d; c.right = &e;
80    d.val = 15; d.left = NULL; d.right = NULL;
81    e.val = 7; e.left = NULL; e.right = NULL;
82    
83    averageOfLevels(&a);
84    return 0;
85}

1