# Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters.

Storing strings is for sure more space-efficient and one needs to make less jumps between nodes.

However, I think it might be way slower.

For example, if you wanted to use a trie for auto-complete. So you want a method trie.get_words_by_prefix(prefix). I've added the implementations I have in mind for both solutions below.

## Runtime Thoughts

• Let $$n$$ be the words in the trie,
• $$m_p$$ the matches for the prefix $$p$$
• $$l_w$$ the length of the word $$w$$

### Contains and Insert

Checking if a word is in the trie (contains) and inserting a word is in both cases in $$\mathcal{O}(l_w)$$. I'm not sure if there might be in practice a significant difference.

### Get Words by Prefix

The amortized worst-case runtime for the char-trie is in $$\mathcal{O}(m_p + l_w)$$ as one has to touch every match. Non-matches are not touched due to the usage of the dictionary for the children.

The worst-case runtime for the string-trie is in $$\mathcal{O}(n)$$ even if there is only a single match. One can see this if there are $$(n-1)$$ children of the root node which are not a match but checked first.

If one restricts the complete Unicode charset to only 26 lowercase latin characters I think the string-trie might also be in $$\mathcal{O}(m_p)$$, but right now I'm not quite sure of this.

## Question

Should a prefix tree (trie) node store only a single character or a string? Are there use-cases where one or the other solution is clearly better?

What model is usually used in practice? Are there reasonable benchmarks? Any big implementations? I have seen pygtrie, but was surprised not to find anything commonly used for Java and only some smaller things for C++.

(By the way, I am aware that there are intermediate solutions, e.g. storing two characters or having the common characters as pointers directly and uncommon stuff maybe a longer string)

## Example

Suppose we have a Trie with the following words:

• cat
• cattle
• tom
• tomcat

### Storing Strings: 5 nodes

.
cat
tle
tom
tomcat


Pythonic pseudo-code:

TrieNode(object):
value: str
is_word: bool
children: List[TrieNode]

def get_words_by_prefix(self, prefix):
if not is_prefix(prefix, self.value):
return []
matched_words = []

if self.is_word:
matched_words.append(self.get_word())
remainder = prefix[len(self.value):]

for child in self.children:
matched_words += child.get_words_by_prefix()
return matched_words


### Storing Characters: 13 nodes

.
c
a
t
t
l
e
t
o
m
c
a
t


Pythonic pseudo-code

TrieNode(object):
value: str  # only one character
is_word: bool

# mapping from the character of the child to the child
children: Dict[str, TrieNode]

def get_words_by_prefix(self, prefix):
if not is_prefix(prefix, self.value):
return []
matched_words = []

if self.is_word:
matched_words.append(self.get_word())
remainder = prefix[len(self.value):]
if len(remainder) > 0:
matched_words += self.children.get(remainder[0], EmptyTrieNode).get_words_by_prefix(remainder)
return matched_words


However, one could even do this just as a dictionary. The get_words_by_prefix would work a bit different and need to keep track of what it already looked at to generate the words again.

## What I tried

I've implemented versions of both ideas (Char/Dict-Trie vs String/List-Trie) in Python and added 466,551 English words (4.9 MB).

The code is in the "trie" branch of mpu. I want to check some more things before I merge it.

                                            | Char/Dict-Trie   | String/List-Trie
------------------------------------------ | ---------------- | ----------------
Size in Byte                               | 548,615,536 Byte | 254,573,936 Byte
Building the Trie                          | 7.8s             | 15.8s
Checking all words if they are in the trie | 3.9s             | 29.1s


### size-comparison

Word file:                       4,863,005 byte
File read into a single string:  4,863,056 byte
Word list:                      33,130,512 byte
Word set:                       45,708,872 byte
String-Trie:                   254,573,936 Byte