Recursion and Tree Search in C?

Kind of new to trees and recursive functions....

I know the basics of how to create a stack and how to create recursive functions.

I am making a pre-ordered traversal search that should return the address of a node in a tree when the value being searched for matches the value of that node.

I'm having trouble with the return part...I tried reading some things on call stacks...but I do开发者_运维技巧n't understand how to implement it. Is it already there or do I have to make this stack? How do I go about making this stack if I have to make it? I read it needs to be proportional to the height of the tree... Is the best way to find the height of the tree to make another function that does this?

Here is some code I've written so far: Tree and NodePtr is a pointer to a node...

NodePtr SearchTree(int v, Tree T)
{
    //printf(" %i \n", T->value);

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

    return NULL;
}

---

First of all, see recursion.

Now, you want to return what the recursive calls to SearchTree() return, because you're using recursion to delegate the problem into two instances of yourself, so if you don't get your return value upstream, nothing can't possibly work:

NodePtr SearchTree(int v, Tree t)
{
    printf(" %i \n", t->value);
    if (t->value == v) {
        return t;
    } else {
        if (t->Left != NULL) {
            NodePtr left = SearchTree(v, t->Left);
            if (left != NULL) {
                return left;
            }
        }
        if (t->Right != NULL) {
            return SearchTree(v, t->Right);
        }
    }

    return NULL;
}

---

You don't need to worry about the call stack; how it works is hidden by the C compiler, and unless you are searching incredibly deep trees it won't bother you.

Your algorithm is more or less correct, but you need to check the returned value from a recursive call to see if it is null, before you visit the other subtree. Something like:

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

---

You do not need to create the call stack yourself. It is a data structure that is maintained by the runtime environment in which your program is executed, such as your operating system, or the java virtual machine, if you are using Java. Whenever a function is called its arguments and its local variables are pushed onto the stack. When the function exists, they are popped off.

You, as a programmer, generally do not have to worry about it. It helps to know what the call stack is to understand exactly what happens during recursive function calls (or any function calls), or to understand where you local variables come from or what happens to them after your function exits.

---

All the special casing in Ira Baxter's answer and Frédéric Hamidi's answer suggest the design is not quite right:

NodePtr SearchTree(int v, NodePtr T)
{
    if (T == NULL || T->value == v)
        return T;
    NodePtr R = SearchTree(v, T->Left);
    if (R == NULL)
        R = SearchTree(v, T->Right);
    return R;
}

This is, I respectfully submit, simpler. Granted, it makes one more function call when dealing with a NULL leaf node, but there are fewer 'if null' tests scattered around.

Also, I think that the argument to the function (nominally a Tree in the original) is the same type as a NodePtr, so I've opted to use just NodePtr and not Tree too. A tree is represented by the NodePtr that is the root node of the tree.