/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

int max(int a,int b)
{
    return (a > b) ? a : b;
}

int height(struct TreeNode* root) 
{
    if (root) 
    {
        return 1 + max(height(root->left),height(root->right));
    }
    else 
    {
        return 0;
    }
}

double BFS(struct TreeNode* root, int level, int* num_elem) 
{
    if(root == NULL) 
        return 0;
    
    if (level == 0) 
    {
       (*num_elem) += 1;
        return root->val;
    } 
    else 
    {
        return BFS(root->left,level-1,num_elem) +BFS(root->right,level-1,num_elem);
    }
}

double* averageOfLevels(struct TreeNode* root, int* returnSize) 
{
    int i = 0;
    *returnSize = height(root);
    
    double* avgArr = malloc(*returnSize *sizeof(double));
    int* numElem = malloc(sizeof(int) * (*returnSize));
    
    for (i = 0; i < *returnSize; i++) 
    {
        numElem[i] = 0;
        avgArr[i] = BFS(root, i, &numElem[i]);
        
        if(numElem[i] != 0)
        {
            avgArr[i] /= numElem[i];
        }
        
    }
    
    return avgArr;
}