Search function for binary tree

[Jacopo]

Hi again guys,
I'm back with another question, this time concerning tree structures.
My tree is a binary tree and the nodes are struct as follows:

struct Node {
    int info;
    struct Node *parent;
    struct Node *right;
    struct Node *left;
};

So, I need to write this function Search that return the node required.
The strategys that I have to use are:
-Postorder visit
-Preorder visit
-Symmetrical
For now I'm trying to use the first strategy.
Then, I have already written this two codes both working:

int main(int argc, char **argv) {
    ...
}

//first node is tree root
struct Node *Search(struct Node *node, int i) {
    if (!node)
        return NULL;
    if (node->info == i)
        return node;
    struct Node *l = Search(node->left, i);
    struct Node *r = Search(node->right, i);
    if (l)
        return l;
    else
        return r;
}

bool found = false;
struct Node *s;


int main(int argc, char **argv) {
    ...
}

//first node is tree root
void Search(struct Node *node, int i) {
    if (!node)
        return NULL;
    if (node->info == i) {
        found = true;
        s = node;
    }
    if (!found) {
        Search(node->left, i);
        Search(node->right, i);
    }
    found =false;
}

The first code is my first implementation, works fine but, is not efficient because even if it find the node, the procedure seems continue until the end of tree.
So, I've written the 2nd code, that can stops when find the node but it, istead, looks really horrible for me!
My question is:
There are other ways more intelligent and more beautiful to see, to implement my 2nd code? Or maybe there are other approaches that I have not considerate?

[Hodor]

Well... I'd normally return the node from Search() if it was found, in which case the code is something like:

int main(int argc, char **argv)
{
    struct Node tree;
    struct Node *match;


    ...
        do necessary stuff here to set up tree
    ...
    
    match = Search(&tree, 5); // search for 5
    if (match) {              // if found
       ...
    } else {                  // not found
       ...
    }


}


struct Node *Search(struct Node *node, int i)
{

    struct Node *match = NULL;

    if (!node)

        return NULL;


    if (node->info == i) {

        match = node;

    } else {

        match = Search(node->left, i);
        if (!match)
                 match = Search(node->right, i);

    }

    return match;

}

(not tested; typed directly into this message box)

[Jacopo]

mh, but the pointer "match" would be always NULL for each call of function, right? So for each call of Search the if condition will be always false and return will be always NULL as well..
EDIT: Ok, your code works fine, even if I cannot explain how..
EDIT2: Well, I've understand this code, obviously the pointer do referred at different memory location at each call...I think..

[Hodor]

mh, but the pointer "match" would be always NULL for each call of function, right? So for each call of Search the if condition will be always false and return will be always NULL as well..
EDIT: Ok, your code works fine, even if I cannot explain how..
EDIT2: Well, I've understand this code, obviously the pointer do referred at different memory location at each call...I think..

Yeah, every time the function is called recursively 'node' is pointing to a different node

You should also implement the function using the other 2 traversal "orders" to help cement your understanding

[Jacopo]

I'll do it!
Thank you so much!