views:

151

answers:

2

I can't figure out how this works, to my mind, once it gets to the answer it doesn't do anything with it.

Node* FindNode(Node *rootNode, int data)
 {
  if (!rootNode)
   return NULL;
  else
  {
   if (rootNode->data == data)
    return rootNode;
   else
   {
    FindNode(rootNode->left, data);
    FindNode(rootNode->right, data);
   }
  }  
 }
+10  A: 
David
Well that's what I thought... but it works, atleast as part of a bigger system.
Shraptnel
It is possible that the return value is ending up in the right place due to your compiler's particular implementation of the `return` statement; however, you can't rely on it always working. Also, because you always were searching both the left and right subtrees you weren't getting any advantage out of using a BST over an array.
David
@Shraptnel: No it doesn't. More precisely, what you posted in your original post doesn't work. Most likely you reproduced the code incorrectly.
AndreyT
@David: I'd find it working by accident highly unlikely, since the result of the second recursive call will override the result of the first. It simply can't work.
AndreyT
It's a copy and paste, I can't see how those returns could get lost in the conversion. I think the answer works btw, but what I'm looking at makes this work.It could be something to do with the way rootNode changes or something... idk.
Shraptnel
@Shraptnel: In that case most likely this function is simply never called. Or the tree is always empty. Or something else of that nature. In fact, most compilers will actually issue warnings about missing return statements in this code.
AndreyT
@AndreyT: Good point. Though if OP was testing by inserting some numbers in increasing order (and I'm assuming this is a regular BST, not a self-balancing one), the second return value would always be the correct one.
David
You are assuming that the tree is ordered. The question does not specify this.
Martin York
He doesn't mention that the tree is a binary search tree, i.e. is ordered. If it isn't, the last two else if, else clauses should instead be:Node* leftResult = FindNode(rootNode->left);if (leftResult != NULL) return leftResult;else return FindNode(rootNode->right);But if the tree is a binary search tree, you're correct, and your code would be much more efficient.
Sean
A: 

This is assuming that the FindNode returns on the first match.

   Node* FindNode(Node *rootNode, int data)
    { 
       Node *ptr;
       if (!rootNode) 
          return NULL; 
       else 
       { 
          if (rootNode->data == data) 
             return rootNode; 
          else 
          {
             ptr = NULL;
             // if either left or right child is there
             if(rootNode->left || rootNode->right)
             { 
                // if not found in left subtree
                if(NULL == (ptr = FindNode(rootNode->left, data))){
                   // check in right subtree
                   ptr = FindNode(rootNode->right, data);
                }
             }
             return ptr;
          }   
       }
    }
Chubsdad