Tiers tree print all suffixed provied wrong output

Question

I need to print all suffixes of a tires tree. I am using following traverse method to print all suffixes.

struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    char label;
    bool isLeaf;
};

void traverse(char prefix[], struct TrieNode *root) {
    concatenate_string(prefix, &(root->label));
    if (root->isLeaf) {
        printf("%s\n", prefix);
    }

    for (int i = 0; i < 26; i++) {
        if (root->children[i]) {
            traverse(prefix, root->children[i]);
        }
    }
}

Consider following Trie tree

    Root
 |     |    |
 L     M    N
|  |
a  b 

So my expected output is

La
Lb
M
N

But my code prints

  La
  Lab
  LabM
  LabMN

As per my understanding root cause for the issue is not updating prefix variable correctly. How to fix this issue?

Answer 1

That is because you keep concatenating. It is better to have char prefix[] as a local variable, e.g:

void traverse(char prefix[], struct TrieNode *root)
{
    char newprefix[30];
    strcpy(newprefix, prefix);
    concatenate_string(newprefix, &(root->label));
    if (root->isLeaf) {
        printf("%s\n",newprefix);
    }

    for(int i=0 ; i< 26 ; i++){
        if(root->children[i]){
            traverse(newprefix, root->children[i]);
        }
    }
}

and call like:

traverse("", root);