Trie Tree Initialization

Question

I am using C++ to construct a trie tree with a bunch of words in dictionary. This is how I defined my TrieNode and built a tree:

struct TrieNode {
    TrieNode *children[26];
    bool isWord;
    TrieNode(): isWord(false) {}  /* to be deleted */
};

void buildTree(TrieNode *root, string word) {
    TrieNode *cur = root;
    for (char c : word) {
        if (!cur->children[c-'a'])
            cur->children[c-'a'] = new TrieNode();
        cur = cur->children[c-'a'];
    }
    cur->isWord = true;
}

This works fine on some compilers, but on others this produces some strange results. For example, one time I found isWord was initialized to be 152, and the whole program crashed. I tried deleting the line marked above in the code, things worked out again. What is going on here?

Also, what is the difference between "new TrieNode()" and "new TrieNode"? Sometimes I found they produce different results too.

*What is going on here?* -- Your program has bugs. That's the gist of it. — PaulMcKenzie, Oct 12 '18 at 17:02
please use `std::array` for your children. And access it with children.at(idx) instead of children[idx], since you don't have any check that the sting will only have small alphabetic characters you might access out of bounds memory, which is probably how you wrote 152 to the isWord bool — Bob Bills, Oct 12 '18 at 17:08
*what is the difference between "new TrieNode()" and "new TrieNode* -- You failed to initialize the array of pointers to `nullptr`'s in your default constructor. That is when you will notice the difference. — PaulMcKenzie, Oct 12 '18 at 17:23
`TrieNode` looks like could be leaking `TrieNode`s. Hard to be sure without a MCVE. It also doesn't observe the [Rule of Three/Five](https://en.cppreference.com/w/cpp/language/rule_of_three), and this can be a fantastically fun bug source. — user4581301, Oct 12 '18 at 17:26

Christophe · Answer 1 · 2018-10-12T18:37:28.147

0

The problem with your code, is that you assume the members to be initialized. Unfortunately, this is not true. So the pointers to the children are not necessarily initialized to nullptr, which causes your code to dereference invalid pointers, which causes undefined behavior (UB) (e.g. memory corruption, crashes, etc...).

Easy solution:

Add a default initializer for your array in the class:

       TrieNode *children[26]{};

Demo

My advices:

use vectors instead of native arrays. Their default constructor ensures they are empty.
read this article about initialisation
make some bound checking, because if some capitals are lost in your data, you'll go out of range, and again, UB.

edited Oct 12 '18 at 18:37

answered Oct 12 '18 at 18:14

Christophe

68,716
7
72
138

Thank you very much! I just figured it out myself. You're right, because I define my own constructor so I need to make sure all members are properly initialized. The alternative is to just use the default constructor which will set all children[26] to be nullptr and isWord to be false. – Junwei Zhang Oct 12 '18 at 18:38

Trie Tree Initialization

1 Answers1