CODEWITHSUNDEEP
cbinary-search-tree
S. James
S. James

Reputation: 77

Printing Sums within range for a Binary Search Tree

I've almost got my code working, but for some reason it isn't actually taking the values of each node and adding them up. Instead, the output for sum is 0 each time. I thought that the sum = sum + data line in the btreeSumRange method would take care of this. Any idea how to fix this?

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

  static long long sum;

  typedef struct node
  {  
      long long data;
      struct node *left;
      struct node *right;
  } node;


node * btreeInsert(node *node,long long data)
{
    if(node==NULL)
    {
        struct node *temp;
        temp = (struct node *)malloc(sizeof(node));
        temp -> data = data;
        temp -> left = temp -> right = NULL;
        return temp;
    }

    if(data >(node->data))
    {
        node->right = btreeInsert(node->right,data);
    }
    else if(data < (node->data))
    {
        node->left = btreeInsert(node->left,data);
    }
    return node;

}

void btreeSumRange(node *tree, long long min,long long max) {
    if (tree == NULL) {
       return;
    }
    btreeSumRange(tree->left, min, max);
    long long data= tree->data;

    if((data>=min)&&(data<=max)){
        sum = sum + data;
    }
    btreeSumRange(tree->right, min, max);
}


int main() {

    node *root;
    long long value;
    root = NULL;

    FILE* data = fopen ("dataA", "r");
    FILE* range = fopen ("rangeA", "r");

    while(fscanf(data, "%lld\n", &value) != EOF){
        printf("%lld\n", value);
        btreeInsert(root, value);
    }

    long long min;
    long long max;

    while(fscanf(range, "%lld %lld\n", &min, &max) != EOF){
        btreeSumRange(root, min, max);
        printf("Range [%lld,%lld]. Sum = %lld. \n", min, max, sum);
    }


    return 0;
}

Upvotes: 0

Views: 81

Answers (1)

kaylum
kaylum

Reputation: 14044

You have two problems in your code.

  1. At the top level the root is not being set by the initial call of btreeInsert. So btreeInsert(root, value); should be root = btreeInsert(root, value);

  2. The malloc call is using the incorrect size:

    temp = (struct node *)malloc(sizeof(node));

    The confusion comes from the fact that there is both a type named node and a variable named node. And in that line it is the variable which is in scope. The variable is a pointer so sizeof(node) gives the pointer size. But you clearly want the struct size not the pointer size. Suggest you avoid such confusion in the future by not overloading type and variable names. One way to fix that would be to change that line to the following (no cast needed BTW):

    temp = malloc(sizeof(*temp));

Upvotes: 1

Related Questions