Recursively searching a binary tree

[fread]

I am trying to find a given node (char key[]) in a binary tree and return it to main. My problem is even after I find the node I can't seem to escape from the recursive method. My logic is obviously wrong, but I was thinking: if I find the node I return it to the previous call, then I check that node before attempting to go(call) left or right, if it is the node I want I return that as well, but it just keeps going like a traversal straight through to the end.

This is my code:

[code]
TreeNodePtr Search(TreeNodePtr node,char key[MaxWordSize+1]){
  if (node != NULL){ 
     if (strcmp(node->data.word,key) == 0) return node;
     Search(node->left,key);
     if (strcmp(node->data.word,key) == 0)return node;
     Search(node->right,key);
      }
}
[/code] 

Any help would be appreciated.

[laserlight]

What happens if node == NULL?

As for the algorithm: just compare the key with the current node's word. If it is equal, you have a match and can return immediately. If not, use that to decide whether to search in the left subtree or the right subtree, but not both (assuming that this is a binary search tree).

[fread]

What happens if node == NULL?

As for the algorithm: just compare the key with the current node's word. If it is equal, you have a match and can return immediately. If not, use that to decide whether to search in the left subtree or the right subtree, but not both (assuming that this is a binary search tree).

Well from the code there that is what i thought i was doing. Lets say after a left call i find the node. I test, its a match, and i try to return to the previous call. On returning it appears the node i return is not the one that the comparsion sees and the node->right receives. it a different node.
i had some printf statements monitoring the values as i stepped through. I could see it is wrong but for all apparant reasons the code looks write. lastly its a binary tree, not a binary search tree.

[matsp]

Excuse my ignorance, but isn't a Binary Search tree and a Binary Tree (essentially) the same thing. At least Wikipedia seems to imply that if you are searching in a binary tree (using it's binary tree structure rather than scanning all nodes, that is), then it is a binary search tree:
http://en.wikipedia.org/wiki/Binary_tree

You are not returning the result from your recursions, so you "loose" the return value.

You should also look at the result of strcmp and then decide to go EITHER left or right - not both (right now you are traversing EVERY node in the tree).

--
Mats

[slingerland3g]

the standard library does offer a void *bsearch function.

[matsp]

the standard library does offer a void *bsearch function.

But that is not going to search a binary tree - it works on a sorted array.

http://www.manpagez.com/man/3/bsearch/

--
Mats

[slingerland3g]

Understood, matsp, I was hoping that reviewing that code would help enlighten those on binary searches in general either for arrays or within linked lists. "Divide and conquer" to the rescue.

[laserlight]

Excuse my ignorance, but isn't a Binary Search tree and a Binary Tree (essentially) the same thing.

No, not all binary trees are binary search trees.

At least Wikipedia seems to imply that if you are searching in a binary tree (using it's binary tree structure rather than scanning all nodes, that is), then it is a binary search tree:

More like: if it is a binary search tree then you can search it using the properties of a binary search tree. After all, just because you use binary search on an unsorted array does not make the unsorted array sorted.

[matsp]

Laserlight, yes, of course, we can have a binary tree that doesn't contain elements in a sorted order. And just like an array, if the elements in the tree aren't in a sorted order.

If the keys in this tree aren't ordered in alphabetical order (which is what I understood them to be, when I said "Binary tree == Binary Search Tree"), then you obviously have to visit every node to see if that node matches. It should be sufficient to compare once per node, however.

--
Mats

[Salem]

> Search(node->left,key);
Perhaps you should examine the return result of the recursive call.
If it returns NULL, carry on looking, else....

[iMalc]

Well from the code there that is what i thought i was doing. Lets say after a left call i find the node. I test, its a match, and i try to return to the previous call. On returning it appears the node i return is not the one that the comparsion sees and the node->right receives. it a different node.
i had some printf statements monitoring the values as i stepped through. I could see it is wrong but for all apparant reasons the code looks write. lastly its a binary tree, not a binary search tree.

laserlight's question was actually a really good hint. Forget what the previous recursive call might have been, in fact forget that it is recursive at all for one minute, in fact forget that you even wrote it. Just look at the code posted and ask yourself "What happens if node == NULL?".
In particular, pay attention to the return type of the function.