Hello,

I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger, the issue seems to be in the insert function. I explained the issue in code comments.

struct Trie{
    struct Node{
        int id, nxt[26];
        Node(int id) : id(id)
        {
            memset(nxt, -1, sizeof(nxt));
        }
    };
    vector<Node> v;
    vector<bool> leaf;
    void init()
    {
        v.clear();
        leaf.clear();
        addNode();
    }

    int addNode()
    {
        v.push_back(v.size());
        leaf.push_back(false);
        return (int)(v.size()) - 1;
    }

    int getSizeMinusOne()
    {
        return (int)(v.size()) - 1;
    }

    void insert(const string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            c -= 'a';
            if (v[cur].nxt[c] == -1)
            {
                // Note I only use one of the following NOT both at the same time
                
                // Approach (1)
                // v[cur].nxt[c] doesn't get updated. Stays -1 and RTEs later on due to out of boundary access
                v[cur].nxt[c] = addNode();

                // Approach (2)
                // works fine
                addNode();
                v[cur].nxt[c] = getSizeMinusOne();
            }
            cur = v[cur].nxt[c];
        }
        leaf[cur] = true;
    }
};

I also found out that both approaches seem to work find when changing the array nxt to a vector instead of an array. Could someone explain why this happens when nxt is an array? And why approach (2) works fine even if nxt is an array?