CODEWITHSUNDEEP
cbinary-search-tree
ShadyBears
ShadyBears

Reputation: 4185

Finding # of integers in range from low to high in BST (C)

Given a high and a low, the point of this function is to find the amount of numbers equal or in between. I use 5 and 10 as my low and high and should receive a return result of 4. Since I'm using recursion I use a static variable to keep track. However I keep getting 1 as a result. Why?

In my test function:

int main()
{
  int i;

  int a[] = {8, 2, 7, 9, 11, 3, 2, 6};


  BST_PTR t = bst_create();

  for(i=0; i<8; i++)
    bst_insert(t, a[i]);

    printf("%d\n", bst_num_in_range(t,5,10)); <----- **calls the function here**
  //rest of tests here

int bst_num_in_range(BST_PTR t, int low, int hi)
{
    static int x = 0;

    if ( NULL == t->root)
        return 0;

    return num_in_range_helper(t->root, low, hi, x);
}

int num_in_range_helper(NODE *r , int low, int hi, static int x)
{
    if (r == NULL)
       return 0;

    if (low < r->val)
       num_in_range_helper(r->left, low, hi, x);

    if ( low <= r->val && hi >= r->val )
        x++;

    if (hi > r->val)
        num_in_range_helper(r->right, low, hi, x);

    return x;
}

Upvotes: 1

Views: 166

Answers (1)

pepo
pepo

Reputation: 699

That static keyword does not make x the same variable in those two functions. You need to assign return values to x after every call, i.e. try something like this

int bst_num_in_range(BST_PTR t, int low, int hi)
{
    if ( NULL == t->root)
        return 0;

    return num_in_range_helper(t->root, low, hi);
}

int num_in_range_helper(NODE *r , int low, int hi)
{
    if (r == NULL)
        return 0;

    int x = 0;

    if (low < r->val)
        x += num_in_range_helper(r->left, low, hi);

    if ( low <= r->val && hi >= r->val )
        x++;

    if (hi > r->val)
        x += num_in_range_helper(r->right, low, hi);

    return x;
}

EDIT: you don't need to send current x to the helper either, you just ask the helper for the number of vertices in two subtrees, add them and return the total number in the current subtree only

Upvotes: 1

Related Questions