Searching a binary search tree - doesn't work

Hello,

I have a binary search tree consisting of nodes that contain first and last name of students on a college. Below I've written a function that receives student's last name, and should return pointer to student's node if the student with such last name is found, or NULL if it is not found. I know there's a way better way to do this in a binary search tree (posted at the bottom), but I've decided to play a bit since I need practice with recursive functions. Anyway, the below function doesn't work and I'd appreciate if you could tell me why. After running the program Windows gives me illegal program operation.

The program has been tested with another function that we used in college classes (posted at the bottom), so it works just fine. I'm just curious why my function doesn't work good.

Code:

---


struct s {
        char firstName[25 + 1];
        char lastName[25 + 1];       
        struct s *left;
        struct s *right;
};

typedef struct s record;


...


record *search(record *root, char lastName[]) {
        if (root) {
                if (!strcmp(root->lastName, lastName)) {
                        printf("Found it!\n");
                } else {
                        root = search(root->right, lastName);
                        if (root == NULL) {
                                root = search(root->left, lastName);
                        }
                }
        }
        return (root);
}

---

Here's the function that works:

Code:

---


record *search(record *root, char lastName[]) {
        int compare;
       
        if (root) {
                compare = strcmp(root->lastName, lastName);
                if (compare < 0) {
                        return (search(root->right, lastName));
                } else {
                        if (compare > 0) {
                                return (search(root->left, lastName));
                        }
                }
        }
        return (root);
}

---

You aren't checking whether or not you need to search the left or right subtrees by using the return value of the strcmp function like the working version of the function does. Your code always goes off searching the right subtree even in the case where the node with the student you are searching for cannot possibly be in the right subtree. The whole point of a binary search tree is to avoid unnecessary searching. If you know for a fact the student cannot possibly be in the right subtree then don't search the right subtree. To do this, you need to check strcmp's return value and search the appropriate subtree based on that value just as the working function does.

You should also not be attempting to set root to another value. What happens if the path in the function that searches the right subtree ends up returning NULL to root? If root is NULL, then how can you expect to call search(root->left,lastname)? If root is NULL then root has no left pointer. Your code would only work if the student you are searching for could be found somewhere on the path from the root and only following right links. It would blow up if you ever had to go left at any point. So, don't try to fool around reassigning root, just return values as the working function does.