Search code examples
cbreadth-first-search

Average of the nodes on each level in binary tree getting the wrong result

I'm a beginner and I'm trying to write a code that return the average of the nodes on each level in binary tree in C language, using the BFS algorithm. I don't getting the right result, what am I doing wrong? In this case, I'm getting 4,66667 for the result, which is all the nodes, except root, divided by 6. I don't understand why it's generating this result. I'm sorry for my bad English. Here is the code:

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
};

typedef struct Node {
    struct TreeNode *node;
    struct Node *next;
} NODE;

typedef struct queue {
    struct Node *front;
    struct Node *rear;
    int length;
} QUEUE;


struct TreeNode* createTree(int value) {


  struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
   newNode->val = value;
   newNode->left = NULL;
   newNode->right = NULL;

  return newNode;
}

struct TreeNode* insertLeft(struct TreeNode* root, int value) {

  root->left = createTree(value);
  return root->left;
}

struct TreeNode* insertRight(struct TreeNode* root ,int value) {

  root->right= createTree(value);
  return root->left;
}

QUEUE *initialize_queue() {
    QUEUE *q = (QUEUE *)malloc(sizeof(QUEUE));
    q->front = NULL;
    q->rear = NULL;
    q->length = 0;
    return q;
}

void enqueue(QUEUE *q, struct TreeNode *root) {
    NODE *new_node = (NODE *)malloc(sizeof(NODE));
    new_node -> node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    new_node->node = root;
    new_node->node->left = root->left;
    new_node->node->right = root->right;
    new_node->node->val = root->val;
    new_node->next = NULL;

    if(q->front == NULL && q->rear == NULL) {
        q->front = q-> rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
    q->length++;
}


struct Node *dequeue(QUEUE *q) {

    struct Node *temp = q->front;

    if(q->front == NULL) {
        return NULL;
    } else {
        q->front = q->front->next;
        if(q->front == NULL) {
            q->rear = NULL;
        }
    }
    q->length--;
    return temp;
}

int get_height(struct TreeNode *root) {
    if(root == NULL) {
        return 0;
    }

    int left = get_height(root->left);
    int right = get_height(root->right);

    if(left > right)
        return (left + 1);
    else
    return (right+1);
}
void averageOfLevels(struct TreeNode* root){


  int Size = get_height(root);
   float result = 0;

    QUEUE *q = initialize_queue();
    enqueue(q, root );

    while(q->length) {

              long int sum = 0, count = 0;

            for(int i = 0; i < Size ; i++) {

            struct Node *temp = dequeue(q);
            sum += temp->node->val;
            count++;
            if(temp->node->left != NULL) {
                 enqueue(q, temp->node->left);
            }
            else if(temp->node->right != NULL) {
                 enqueue(q, temp->node->right);
            }
        }

      result = sum*1.0 / count;

         }
   printf("%lf", result);
 }
void free_tree(struct TreeNode* root) {

    struct TreeNode* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}
int main( ) {

     struct TreeNode* root = NULL;

        root = createTree(2);
        insertLeft(root,4);
        insertRight(root,6);
        insertLeft(root->left, 8);
        insertRight(root->right, 10);

       averageOfLevels(root);

       free_tree(root);

}
Solution

  • Your algorithm is mostly sound, but fails at two junctures.

    1. It does not properly process both children of any given node when pushing them into the tree. There is a misplaced else that simply should not be there.
    2. It does not mass, nor report, the culmination of per-level averages even if you fix (1). Instead, it basically finds the single average of all nodes in the entire tree.
    3. Not a deal breaking issue, but your queue is grossly inefficient in that it is needlessly making duplicates of the nodes. It does not need to do any of that. It can use node pointers directly from the tree as the node pointers internal in the QUEUE objects.

    Additionally, get_height is not needed. You should track the level of the tree you're processing by incorporating that into the QUEUE objects holding pointers to the tree nodes When you first push the root to prime the queue, the initial level stored along side the node pointer is zero (0). From that point on, as you pop items to process them and push their children into the queue, those children will get the just-popped parent level + 1. Only when the active queue top reported level is greater than the one you are currently processing do you stop summing, compute the average, and report it for that level. Then, reset the sum to zero, bump the now-processing level value, and continue. This process repeats until the queue is expired, at which point the last level is reported and you're done with the algorithm.

    With additional modifications, the result is the following. This is just one of several ways to do this, but it is fairly simple to understand, and is very space efficient:

    #include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

typedef struct Node
{
    struct TreeNode const *node;
    struct Node *next;
    int level;
} NODE;

typedef struct queue
{
    struct Node *front;
    struct Node *rear;

} QUEUE;

struct TreeNode *createTree(int value)
{
    struct TreeNode *newNode = malloc(sizeof *newNode);
    newNode->val = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct TreeNode *insertLeft(struct TreeNode *root, int value)
{
    root->left = createTree(value);
    return root->left;
}

struct TreeNode *insertRight(struct TreeNode *root, int value)
{
    root->right = createTree(value);
    return root->left;
}

QUEUE initialize_queue()
{
    QUEUE q = { NULL, NULL };
    return q;
}

void enqueue(QUEUE *q, struct TreeNode const *root, int level)
{
    NODE *new_node = malloc(sizeof *new_node);
    new_node->node = root;
    new_node->level = level;
    new_node->next = NULL;

    if (q->front == NULL)
    {
        q->front = new_node;
    }
    else
    {
        q->rear->next = new_node;
    }
    q->rear = new_node;
}

struct Node *dequeue(QUEUE *q)
{
    if (q->front == NULL)
        return NULL;

    struct Node *temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL)
    {
        q->rear = NULL;
    }

    return temp;
}


void averageOfLevels(struct TreeNode const *root)
{
    if (!root)
        return;

    long int sum = 0, count = 0;
    int level = 0;

    QUEUE q = initialize_queue();
    enqueue(&q, root, level);

    while (q.front)
    {
        struct Node *top = dequeue(&q);
        if (top->level > level)
        {
            if(count > 0)
            {
                double avg = (double)sum / count;
                printf("Level %d : %f\n", level, avg);
            }

            sum = 0;
            count = 0;
            ++level;
        }

        sum += top->node->val;
        ++count;

        if (top->node->left)
            enqueue(&q, top->node->left, level+1);

        if (top->node->right)
            enqueue(&q, top->node->right, level+1);
    }

    // report last level 
    if (count > 0)
    {
        double avg = (double)sum / count;
        printf("Level %d : %f\n", level, avg);
    }
}

void free_tree(struct TreeNode *root)
{
    struct TreeNode *temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right)
    {
        free(temp);
        return;
    }
}

int main()
{
    struct TreeNode *root = NULL;

    root = createTree(2);
    insertLeft(root, 4);
    insertRight(root, 6);
    insertLeft(root->left, 8);
    insertRight(root->right, 10);
    averageOfLevels(root);
    free_tree(root);
}

    Output

    Level 0 : 2.000000
Level 1 : 5.000000
Level 2 : 9.000000

    I suspect that is what you're really after. If you want to exclude the root node from reporting you certainly can, but I leave it as an exercise for you. Likewise for how to accumulate the results into an array and produce them back to the caller. Right now the example just reports them to the console.