Recursively searching a binary tree
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:
PHP 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.
Re: Recursively searching a binary tree
Quote:
Originally Posted by
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).
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.