Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Depth-first search (DFS) in C

Search a tree of groups recursively by checking each group's own items first, then its subgroups, and optionally save a pointer to the group containing the first match.

Version: ISO C23; implementation support may vary

Syntax

#include <stddef.h>

typedef struct Group {
    const char *name;
    const int *items;
    size_t item_count;
    struct Group **subs;
} Group;

static bool find_item(Group *group, int target, Group **out);

find_item performs depth-first search (DFS) on a tree of groups. Each call checks the current group's own items first, then visits its subgroups in array order. Recursion searches a whole subtree before moving to the next sibling, unless it finds the target first. A true result propagates back immediately; false means there was no match in that subtree.

In the self-referential structure, struct Group **subs points to the first element of an array of pointers to groups, not an array of Group objects. Inside the definition, the struct Group tag is already usable, but the type is still incomplete and the Group alias from this typedef is not yet in scope. The structure can contain a pointer member, but it cannot directly contain an object of its own type.

NULL is a macro defined in <stddef.h> that expands to a null pointer constant. subs == NULL means there is no subgroup array; in an existing array the first NULL entry is an end sentinel, not a gap to skip. Keep the groups and arrays alive during the search, and keep the matched group alive for as long as you use the saved pointer. A missing sentinel can cause an out-of-bounds read. For each group with a nonzero item_count, items must point to the start of a range of at least item_count readable int elements.

The write is optional, not the argument: pass &found for a Group *found variable, or pass NULL to check existence only. The function writes the matching group through *out only on a match and only if out != NULL. On false it leaves the caller's variable unchanged, so it may still contain an earlier result.

Worst-case time is O(G + I) for G groups and I local items, with O(h) simultaneous calls for tree height h. For very deep inputs, consider an explicit stack; for a graph with cycles, track visited nodes. The example uses ISO C23 syntax; implementation support may vary.

Examples

#include <stddef.h>
#include <stdio.h>

typedef struct Group {
    const char *name;
    const int *items;
    size_t item_count;
    struct Group **subs;
} Group;

static bool find_item(Group *group, int target, Group **out)
{
    for (size_t i = 0; i < group->item_count; ++i) {
        if (group->items[i] == target) {
            if (out != NULL) {
                *out = group;
            }
            return true;
        }
    }

    if (group->subs != NULL) {
        for (size_t i = 0; group->subs[i] != NULL; ++i) {
            if (find_item(group->subs[i], target, out)) {
                return true;
            }
        }
    }
    return false;
}

int main(void)
{
    const int sevens[] = {7};
    const int answers[] = {42};
    Group deep = {"deep", answers, 1, NULL};
    Group right = {"right", answers, 1, NULL};
    Group *left_subs[] = {&deep, NULL};
    Group left = {"left", sevens, 1, left_subs};
    Group *root_subs[] = {&left, &right, NULL};
    Group root = {"root", sevens, 1, root_subs};

    Group *found = NULL;
    if (find_item(&root, 7, &found)) {
        printf("7 -> %s\n", found->name);
    }
    if (find_item(&root, 42, &found)) {
        printf("42 -> %s\n", found->name);
    }
    printf("42 exists: %s\n", find_item(&root, 42, NULL) ? "yes" : "no");
    if (!find_item(&root, 99, &found)) {
        printf("99 missing; saved group: %s\n", found->name);
    }
    return 0;
}

Result

7 -> root
42 -> deep
42 exists: yes
99 missing; saved group: deep

`7` matches in `root` before any subgroup is checked. For `42`, the `left` subtree reaches `deep` before `right` is visited. The call with `NULL` checks existence only, and the failed search for `99` leaves `found` pointing to `deep`.

Related lessons

  • C · Lesson 79 · Advanced · Version: 3

Sources