acrmuui acrmuui - 2 months ago 8
C Question

Searching recursive data structure in C

I would like help to write a recursive search function.

I have a data structure that looks like this:

struct node_t {
char name[16];
int num_children;
node_t** children;
};


and I have many nodes in a deep tree-like structure, where each node can have many children.

To find a node somewhere in the tree, I currently pass the root node to this function:

node_search(node_t* parent, const char* node_name) {

if(strcmp(parent->name, node_name) == 0) {
return parent;
}
else {
for(int i = 0; i < parent->num_children; ++i) {
node_t* node_found = node_search(parent->children[i], node_name);

if(strcmp(node_found->name, node_name) == 0) {
return node_found;
}
}
}
}


This seems to work, but two things I have observed make me worry that this is not the best/correct way to do this:


  1. When the desired node is found very deep in the tree, the
    strcmp
    is done for each frame in the call stack on the way out of the recursion.

  2. When traversing a branch in the tree that doesn't have the desired node, the
    strcmp
    inside the loop ends up doing its compare on garbage values, which just doesn't feel very solid.



Does anybody know it this recursive search could be done in a better way?

Answer

You need a return value on all paths, and addressing that warning that your compiler should have given you will lead you to understand NULL is the only logical alternative when nothing is found.

With that, you can significantly reduce the code by eliminating redundant checks while fixing this. You don't need two strcmp here. You mentioned in your bullet list: "...the strcmp inside the loop..." - you already have a strcmp in the loop; it's done in the recursed call for that child. There is no sense in doing it again.

node_t* node_search(node_t* parent, const char* node_name)
{
    if(strcmp(parent->name, node_name) == 0)
        return parent;

    node_t *node_found = NULL;
    for(int i = 0; !node_found && i < parent->num_children; ++i)
        node_found = node_search(parent->children[i], node_name);

    return node_found;
}

That should return NULL if the element is not found, and break the loop, returning up the chain as soon as a node is found.

Finally, depending on the location of this code, you might want to ensure parent isn't NULL before that opening dereference. This code assumes it is never called without a valid, non-null pointer for parent. Whether or not that is a valid assumption (it was in your posted code, apparently) I leave for you to decide.