Pre Order Search on a general tree

[TiredStudent]

HI, I am supposed to use a pre order transversal to search for an inputted value. The function returns a pointer to the node it is found in. If it is not found it should return NULL (I think). My code works fine if you only travel left. If the number is to the right at all or not in the tree, I get a segmentation fault. I can't figure out why it is doing this. Been working on it all day. Thank you in advance for any help!

/********************************************************************/
/*            SearchTree
/********************************************************************/
/*
 * Input:       The value being searched for, and the pointer to the root (intially) 
 * Output:      A pointer to the node where the value is found
 * Task:        Uses a preorder transveral to search for the inputted value
 */
   NodePtr SearchTree(int value, Tree T)
   {
   
   
      if(T != NULL)
      {
         if(T->value == value) 
            return T;
         return SearchTree(value,T->Left);
         return SearchTree(value,T->Right);
      	
      }
      
      else 
      {
         
         return T; 
      }
   }

[claudiu]

Can you post the definitions for Tree and NodePtr? It's impossible to tell their types from this.

[TiredStudent]

typedef struct node Node;
typedef Node* NodePtr;
typedef Node* Tree;
struct node
{
    int value;
    NodePtr Left;
    NodePtr Right;
};

Tree is just a pointer to the root of the tree.

[claudiu]

Well your algorithm is wrong. The second return never happens, it's just dead code. When you reach the bottom left side of your tree you return NULL and exit. You never go in the right side.

[TiredStudent]

Could you please give me a suggestion on how to fix it, or how the algorithm should be? I am at my wit's end with it. Just a suggestion, I am not asking you to fix the code for me. Thank you.

[claudiu]

Sure. Well I'm assuming this is a Binary search tree, so the information is already ordered in the tree?

If so, then you have compare the value you are looking for with the current node and decide where to go accordingly. Here is some Pseudo-code for you:

SEARCH(NODE)
WHILE CURRENT NODE IS NOT NULL
   IF CURRENT NODE HAS VALUE val
      return CURRENT NODE
   ELSE IF CURRENT NODE VALUE < val
      return SEARCH(CURRENT NODE -> LEFT)
   ELSE
      return SEARCH(CURRENT NODE -> RIGHT)
END WHILE

Something like that. Then you have to add in the special case when you don't find it. That's when you have reached leaf level and the current node is not value.

[TiredStudent]

It is not a binary search tree. That is what has made it so frustrating. To find the value we essentially have to search the whole tree. Any example I find always assumes it is a BST. :-(
Any other suggestions? Thank you SO much for taking the time to help me!

[claudiu]

Oh OK, no problem. So what you need then is to look through the entire tree, like you were attempting.

Well, in that case it should be something like this:

SEARCH(NODE, value)
IF NODE = NULL 
   return NULL
IF NODE->val = value
  return NODE
ELSE 
   LEFT = SEARCH(NODE->LEFT, value)
   RIGHT = SEARCH(NODE->RIGHT,value)
IF LEFT != NULL
   return LEFT
ELSE 
   return RIGHT

Not sure if that works, I am still wrapping my head around it... it's 5 AM here

[TiredStudent]

IT WORKS!!!!!! Thank you! You are a lifesaver! Just have to tweak it a bit, still getting a seg fault for a value not in the tree. X-D

[claudiu]

Wow... I am really glad it worked out for you, I just completely pulled that out of my ass, but it looks like the comp sci. college education still pays off years later. Yay!

I think there is an improvement you can make to it. When you are calculating LEFT and before searching in RIGHT, if LEFT is not NULL you should just return LEFT(the val is already found so there is no need to search all of RIGHT too). If LEFT is NULL then you can just return SEARCH(RIGHT), because val is either there or nowhere at all in which case you will carry over the return NULL you get from the right side

So basically

LEFT = SEARCH(NODE->LEFT, value)
IF LEFT != NULL
   RETURN LEFT
ELSE RETURN SEARCH(NODE->RIGHT,value)

[TiredStudent]

It is not working. It is again only checking the left hand nodes. :-( If not in the left hand nodes it returns the last left hand node. *Sigh* What do you think? Is there an error in the way I translated it?

   NodePtr SearchTree(int value, Tree T)
   {
      if(T==NULL)
         return NULL;
      if(T->value ==value)
         return T;
      else 
      {
         T->Left = SearchTree(value,T->Left);
         T->Right = SearchTree(value,T->Right);
      }
      if (T->Left != NULL)
         return T->Left;
      else if (T->Right != NULL)
         return T->Right;
      else   
      	 		
         return T;
   }

[claudiu]

It is not working. It is again only checking the left hand nodes. :-( If not in the left hand nodes it returns the last left hand node. *Sigh* What do you think? Is there an error in the way I translated it?

   NodePtr SearchTree(int value, Tree T)
   {
      if(T==NULL)
         return NULL;
      if(T->value ==value)
         return T;
      else 
      {
         T->Left = SearchTree(value,T->Left);
         T->Right = SearchTree(value,T->Right);
      }
      if (T->Left != NULL)
         return T->Left;
      else if (T->Right != NULL)
         return T->Right;
      else   
      	 		
         return T;
   }

Yes, there is a problem. Left and right should not be T->left and T->right because then you are messing up your tree.

   NodePtr SearchTree(int value, Tree T)
   {
      if(T==NULL)
         return NULL;
      if(T->value ==value)
         return T;
      else 
      {
         NodePtr left = SearchTree(value,T->Left);
         if(left != NULL)
                 return left;
         else return SearchTree(value,T->Right);
      }
   }

try now

[TiredStudent]

Ok. It is definitely working now, as long as the number is present. Still working on the case of it not being there. Yay for progress!

[claudiu]

Good job!

It should be fine if it's not in the tree as well. Just check for NULL before using the return value in your main function (or wherever you call the search function). If you use that pointer and its NULL you get a segfault which sounds like what you are doing now.

[TiredStudent]

It did work fine! My problem was in my driver. I was printing out the "found value" and its children. I had a check for NULL, but it was after those print statements, so it was trying to print something that wasn't there and giving a seg fault! Wish I would have realized that sooner! But glad it is working now! Thanks so much! You have been a HUGE help!