CODEWITHSUNDEEP
c++recursiontree
dogsbollocks
dogsbollocks

Reputation: 31

Returning a value from a recursive function

Another recursion problem, sorry just cant get my head round this. I'm trying to return a node pointer whose id matches the supplied id. I think I'm traversing the tree correctly. Any ideas where I'm going wrong here?

//h
Node* findNode(const QString &id, Node *node=NULL)

//cpp
Node* Tree::findNode(const QString &id, Node *node)
{
    if (node == NULL)
        node = root;

    for(int i = 0, end = node ? node->childCount() : -1; i < end ; i++)
    {
        QString nodeId = node->child(i)->id();

        if (nodeId == id)
        {
            return node;
        }
        else
        {
            return findNode(id, node->child(i));
        }
    }
}

Thanks for looking

Upvotes: 0

Views: 1014

Answers (4)

Mats Petersson
Mats Petersson

Reputation: 129524

I'm pretty sure you need something like:

 ...
 else
 {
     Node *temp = findNode(id, node->child(i));
     if (temp) return temp;
 }

As it is, it's returning before it reaches the end of your loop.

Also, you need to return NULL (or better yet, nullptr) at the end of your function:

// At the end
return NULL;

Upvotes: 3

Michael Brandl
Michael Brandl

Reputation: 116

You seem to do only a depth first search, and return the result of the leftmost leaf node.

In findNode(id, node->child(i)); you never check if this returns NULL.

Return only from there if the return value from the child is not NULL (you actually found something), otherwise, continue in the loop (right now, you only look at the first element).

Then, after the loop, if nothing has been found (no return yet), return NULL.

Upvotes: 0

user529758
user529758

Reputation: 

else return findNode(id, node->child(i));`

this will lead to the traversal of the first subtree (child) only.

I would rather write something like this in order to traverse all subtrees in order, until something is found. If nothing is found, return nullptr:

Node *find(Node *tree, string id)
{
    if (tree->id == id)
        return tree;

    Node *ptr = nullptr;
    for (int i = 0; i < tree->childCount; i++)
        if ((ptr = find(node->children[i], id)) != nullptr)
            return ptr;

    return nullptr;
}

Upvotes: 1

Vyassa Baratham
Vyassa Baratham

Reputation: 1467

In the else, only return the value from the recursive call if something was found. Otherwise, you'll never get past i=0

Upvotes: 4

Related Questions