CODEWITHSUNDEEP
cbinary-treebinary-search-tree
ShadyBears
ShadyBears

Reputation: 4185

BST nth smallest (C)

This function tries to find the nth smallest number in a BST. I understand it's essentially just an in order traversal with a counter. If that's the case, then why isn't this code working?

Assuming my BST is correctly implemented (which it is), why does it print out 9? It should print out 6.

int bst_ith_smallest(BST_PTR t, int i)
{
    if(i > count)
        fprintf(stderr, "Input is greater than BST size");

    return (smallest_helper(t->root, i));
}


int smallest_helper(NODE *r, int i)
{
    if(r==NULL) 
        return;

    smallest_helper(r->left, --i);

    if(i == 0)
        return r->val;

    smallest_helper(r->right, --i);
}


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_ith_smallest(t, 3)); <------ HERE the function is called
  //other tests here
}

Upvotes: 0

Views: 155

Answers (1)

ericbn
ericbn

Reputation: 10998

Two problems in your smallest_helper code: you should be decrementing your counter only when the node is visited, and you should be propagating the return value. Also, be careful with return with no value when the function should be returning one.

Try this:

int smallest_helper(NODE *r, int i)
{
    if (r == NULL) {
        return -1;
    }
    int val;
    val = smallest_helper(r->left, i);
    if (val >= 0) {
        return val;
    }
    if (--i == 0) {
        return r->val;
    }
    val = smallest_helper(r->right, i);
    if (val >= 0) {
        return val;
    }
    return -1;
}

That assumes your BST has no negative values, hence a negative value is used to indicate an invalid condition.

Upvotes: 1

Related Questions