Segmentation fault while trying to insert a word into trie

Hi :) Could anyone tell me why the following code doesn't work? The program crashes at the if(children[word[letter_no] - 'A'] == nullptr) line in node corresponding to 'B'. But the node is created, and when I try to call children[1] in the constructor, it works. But when it's called in insert() function, it doesn't...

include

#include <memory> //shared_ptr
#include <string>    
using namespace std;    
const int ALPHABET = 26;

class Node {
public:
    shared_ptr<Node> children[ALPHABET];
    
    Node() { for (int i = 0; i < ALPHABET; ++i) children[i] = nullptr;}
    void insert(const string &word, unsigned letter_no) {
        if (letter_no < word.length()) {
            if (children[word[letter_no] - 'A'] == nullptr) 
                children[word[letter_no] - 'A'] = make_shared<Node>();
            children[word[letter_no] - 'A']->insert(word, letter_no+1);
        }
    }
};

int main() {
    Node trie{};
    trie.insert("ABC", 0);
    return 0;
}

Solution

Enable your compiler warnings!

You got undefined behavior due to unspecified order of evaluation:
```
children[word[letter_no] - 'A']->insert(word, ++letter_no);
```
warning: unsequenced modification and access to letter_no [-Wunsequenced]
You also have a potentially dangerous comparison here:
```
letter_no < word.length
```
warning: comparison between signed and unsigned integer expressions

on wandbox

Also, you should not use new and delete in modern C++ code. Use std::unique_ptr or std::shared_ptr depending on what ownership semantics you require.

From the comments:

Jecke: That's all true, but none of it is what's causing the problem. I simplified my code so it would be more readable in a question. In my original code, I'm trying to use shared_ptr, but the result is the same. Look, pastebin.com/MFZdrp22 doesn't work any better (still segmentation fault)

Look carefully at these lines:

if (letter_no < word.length()) 
{
    if (children[word[letter_no] - 'A'] == nullptr)
    {
        children[word[letter_no] - 'A'] = make_shared<Node>();
    }

    ++letter_no;                                              // (0)
    children[word[letter_no] - 'A']->insert(word, letter_no); // (1)
}

word is "ABC".
word[letter_no] - 'A' is 0.
At (0), you increment letter_no.
At (1), word[letter_no] - 'A' is 1.
children[1] is nullptr. Boom!

Again, the compiler is your friend. Compile with -fsanitize=undefined and you'll get the following error message:

runtime error: member call on null pointer of type 'Node'
runtime error: member access within null pointer of type 'Node'

on wandbox