Thread: Searching a binary search tree - doesn't work

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    34

    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);
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 03:20 PM
  3. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  4. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM