CODEWITHSUNDEEP
cbinary-search-tree
sat
sat

Reputation: 336

Range Search in BST

I need to do range-search function in a binary search tree,which will give the no of items in the given range.i don't understand how to increment the count value when found thus items.because, i have to use recursion function & if i initialize the count variable to 0 in the process of recursion it will always start the count value form 0 not the one that has been updated in count.

    int rangeSearch(struct treeNode * node, int leftBound, int rightBound) 
    {

        int count=0;
        if( node->item >= leftBound & node->item <= rightBound)
        {
            printf("%d ",node->item);
            count++;
        }
        if( node->left!=0 & node->item > leftBound) rangeSearch( node -> left, leftBound , rightBound );
        else if( node->right!=0 & node->item < rightBound )rangeSearch( node -> right, leftBound , rightBound );
        return count;


    }

Upvotes: 3

Views: 4874

Answers (2)

leonardo.lucania
leonardo.lucania

Reputation: 36

It's my first answer so I'm sorry for my bad english.

In every recursive problem like this, the easiest way to think about the problem is:

-resolve the "base case", which is generally trivial. (For most of the data structures this in generally the empty structure, or the one-element's structure.)

-resolve the general case IN TERM OF the substructure that compose the structure, (For example, when considering Trees, this is done considering the LEFT subtree and the RIGHT subtree) ASSUMING that you can count on the solution for the substructure.

I'm sure I've not explained it well, so let me do a trivial example:

We want to count the TOTAL number of elements in a BST. The resolution method is this:

int countElement(struct treeNode* node)
{
    if(node == null)
    {
        //we are in the base case: the tree is empty, so we can return zero.
        return 0;
    }
    else
    {
        /*the tree is not empty:
          We return 1 (the element that we are considering)
          + the elements of the left subtree 
          + the elements of the right subtree.*/

          return 1 + countElement(node->left) + countElement(node->right);
    }   
}

If this is clear to you, we can proceed with your request:

int rangeSearch(struct treeNode * node, int leftBound, int rightBound)
{
    if(node == 0)
    {
        //base case: the tree is empty, we can return 0
        return 0;
    }
    else
    {
        /*our tree is not empty.
          Remember that we can assume that the procedure called on
          the left and right child is correct.*/

          int countLeft = rangeSearch(node->left, leftBound, rightBound);
          int countRight = rangeSearch(node->right, leftBound, rightBound);

          /*So what we have to return?
          if the current node->item is between leftbound and rightbound,
          we return 1 (our node->item is valid) + rangeSearch called
          on the left and child subtree with the same identical range.*/

          if(node->item > leftBound && node->item < rightBound)
          {
              /*the element is in the range: we MUST count it 
                in the final result*/
              return 1 + countLeft + countRight;
          }
          else
          {
              /*the element is not in the range: we must NOT count it 
                in the final result*/
              return 0 + countLeft + countRight;
          }
    }
}

Remember that the key part of all is that if you define and resolve well the base case, then when you will consider bigger structure, you can ASSUME that your recursive procedure called on the SUBSTRUCTURE of that do the right things and returns the right value.

Upvotes: 2

Codor
Codor

Reputation: 17605

To my understanding, as count is local in rangeSearch, the implementation has to be changed as follows to achieve the desired evaluation.

int rangeSearch(struct treeNode * node, int leftBound, int rightBound)
{

    int count=0;
    if( node->item >= leftBound & node->item <= rightBound)
    {
        printf("%d ",node->item);
        count++;
    }
    if( node->left!=0 & node->item > leftBound)
        count += rangeSearch( node->left, leftBound, rightBound );
    if( node->right!=0 & node->item < rightBound )
        count += rangeSearch( node->right, leftBound, rightBound );
    return count;
}

Upvotes: 0

Related Questions