CODEWITHSUNDEEP
cbinary-search-tree
Semih
Semih

Reputation: 87

Find String in BST

I have built a BST that holds album names and years and It constructed according to years.But I want to enter album names and it should give a year. So I built this code part :

int FindString(treeAlbum *node,char albumTitle[])
{

    FindString(node->Left,albumTitle);
    FindString(node->Right,albumTitle);
    if(!strcpy( node->albumTitle, albumTitle))
    {
        return node->year;
    }
}

And treeAlbum struct 

struct treeAlbum{
        char albumTitle[100];
        int year;
        struct treeAlbum *Left;
        struct treeAlbum *Right; 
}

Finally, This code give an error ( Segmentation Fault). How can I fix this ? Thank You.

Upvotes: 0

Views: 337

Answers (3)

ensc
ensc

Reputation: 6984

You want to use strcmp, not strcpy. You should evaluate the result of two FindString() calls and continue only, when they failed.

Upvotes: 0

kviiri
kviiri

Reputation: 3302

The first thing you do in FindString is call FindString again with node->Left. Either node->Left eventually is null (if your tree is correctly constructed) which will cause a segfault or it is an earlier node in the tree (in which case your recursion will cause the stack to fill up). Checking for the null case is certainly required!

Upvotes: 0

Michael
Michael

Reputation: 2261

My best guess for the segmentation fault is that you aren't checking for your base case.

int FindString(treeAlbum *node,char albumTitle[])
{
    if (!node)
    {
        // Return something sane here
        return ERROR_NOT_FOUND;
    }

    FindString(node->Left,albumTitle);
    FindString(node->Right,albumTitle);
    if(!strcpy( node->albumTitle, albumTitle))
    {
        return node->year;
    }
}

However, your code has some other issues:

  1. What are you doing with the return values from the recursive calls to FindString. Right now you're not doing anything.
  2. You're using strcpy, but you probably mean strcmp.
  3. You have a binary search tree, but you're doing a post-fix search. This is linear in the size of your tree, but you should be able to use the sorted-ness of the BST to get a log(n) binary tree search. Namely, look at the album at the current node, and see if you're done, should search left, or search right.

Upvotes: 1

Related Questions