What a trie is and how to design its node

Why it matters

A phone suggests the next word while you type. A search box finishes your query before you press enter. Both need one fast answer to a single question: which stored words start with these letters? A set can tell you whether a whole word is stored, but it cannot list the words that begin with ca without looking at every word. A trie answers that question directly, and it does so in time that depends on the length of what you typed, not on how many words are stored. This module teaches you to build one in Python, use it for search and suggestions, and apply the same idea to numbers.

Start with the problem

Suppose you store the words car, card, care, cat and dog. Someone types ca. You want car, card, care and cat back. Here are three ways to do it, and what each one costs.

The first way is a plain list. You loop over every word and check whether it starts with ca. With n words and an average length of L characters, one query costs about n * L character comparisons. For a dictionary of 100,000 words that is millions of steps for one keystroke.

The second way is a sorted list. Words that start with ca sit next to each other in sorted order, so you can use binary search (the bisect module in Python does this) to find the first one. That is much better than a plain list. But you still have to walk forward to collect the matches, and inserting a new word means shifting elements to keep the list sorted.

The third way is a set. A set is a collection that checks membership in about one step by computing a hash code from the whole word. A hash code is a number that Python computes from the text of a word, and it decides where the word is stored. A set is excellent for "car" in words. It is useless for asking which words start with ca, because the hash code of ca says nothing about the words that were hashed from car or cat. Every word has to be checked.

A trie is a different kind of structure. It stores the letters themselves, arranged so that words sharing a beginning share the same path from the top. Once you have walked down c and a, every word that starts with ca is below you in the tree. Nothing else needs to be checked.

The idea

A trie (said "try", from re-trie-val) is a tree where each step down adds one character. A tree is a structure made of nodes joined by links, with one starting node at the top called the root. Every node below the root has exactly one link pointing up to its parent. A node is a small object that holds some data and links to its children. A child is a node one step further from the root, and the edge is the link between a parent and a child.

Think of a filing cabinet with nested drawers. The top drawer is labelled with nothing. Inside it there is one drawer for each first letter. Inside the c drawer there is one drawer for each second letter, and so on. To find everything filed under ca, you open the top drawer, open c, then open a. Everything inside that last drawer starts with ca. A word is a path of drawers you open, one letter at a time.

Store cat, car and dog. Here is the trie, drawn as text. Each line is one node, and indentation shows the depth. A star marks a node where a stored word ends.

root
  c
    a
      r *
      t *
  d
    o
      g *

The path root, c, a, t spells cat. The path root, c, a, r spells car. The two words share the first two steps, so they share the first two nodes. The d branch is separate because no stored word starts with d except dog.

The starred nodes are the ends of words. The node for t is starred because cat ends there. The node for a has no star, because ca is not a stored word. Yet the path to ca exists, because cat and car both pass through it. That gap between "a path exists" and "a word ends here" is the most important detail in this whole module. Each node therefore carries a flag, usually called is_word, that says whether a stored word ends at that node.

Here are the terms you need from now on. Write them down if that helps.

• Root: the empty starting node. It stands for the empty string.
• Child: a node one character further down.
• Path: the sequence of characters on the way from the root to a node. For the t node under ca in the drawing, the path is cat.
• End-of-word flag: a True or False value on each node. It is True when the path to that node spells a stored word.
• Prefix: a path that may or may not be a word. ca is a prefix of car and of cat, and it is also a path in the trie. It is a word only if its flag is set.

Designing the node

Each node needs two things:

1. Its children, one for each possible next character.
2. The end-of-word flag.

The flag is easy. It is a single bool value, written True or False in Python. The children are the real design choice. You have two main options.

Option A: a list of 26 slots

If you only store the lowercase letters a to z, you can give each node a list with 26 slots. A list is Python's ordinary array: a numbered row of items, counted from 0. Slot 0 is for a, slot 1 for b, and so on up to slot 25 for z. To find the slot for a character ch, you compute ord(ch) - ord("a"). The function ord returns the number that stands for a character. The letter a is 97 and the letter c is 99, so ord("c") - ord("a") is 2. That index is what you use to look up or create the child.

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_word = False

The word class introduces a new kind of object. __init__ is the method that runs when you write TrieNode(), and self is the node being set up. [None] * 26 makes a list of 26 slots, each holding None, which means "no child for this letter yet".

A lookup is one list index, which is very fast. The cost is space: a node always has 26 slots, even if it has only one child. Most nodes in a real trie have only one or two children, so many of those slots are wasted.

Option B: a dict of children

A dict is Python's key-value table. You look up a value by its key, and a dict stores only the keys you add. If your text can contain capital letters, digits, spaces, or characters from other alphabets, 26 slots are not enough. Then each node can hold a dict from a one-character string to a child node. A string of length 1 is the Python form of a single character, so "c" is a character. A dict stores only the children that exist, so a node with one child stores one entry. The price is that each step down needs a hash lookup, which is slower by a constant factor than a list index.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

The dict is written {}. Its keys are strings such as "c", and its values are TrieNode objects. You do not have to declare the types. Python accepts any object as a value. Type hints such as dict[str, "TrieNode"] can document this for readers, but they do not change how the program runs.

Here is how the two options compare.

If you know Java, a dict here plays the role that HashMap plays there. The difference is that Python has no char type. A character is a one-letter string, and that is also the key you use.

Trying the dict version

Here is the counting program with dict children. Only the node class and the insert function use the dict. The counting function loops over the dict's values instead of over a list.

The program prints:

nodes: 7

The answer matches the list version, because the trie is the same. Only the way each node finds its children has changed. The key line is if ch not in cur.children:. It checks whether the dict already has a key for the character ch. If not, the next line creates a new TrieNode and stores it under ch. In both cases cur = cur.children[ch] then moves down to that child. Read the loop as "find or create the child for this letter, then move into it".

The program keeps the words in a list so it runs without any input. The Java version of this lesson reads the words from the keyboard. Python can do the same with input(), but a program that needs typed input cannot be checked by running it on its own, so the examples here use fixed lists.

Compare the two versions on the same input. Both print 7, so the output cannot tell them apart. The difference is in memory and speed, which the next section explains. A good habit is to write the simpler version first, check that its output is right, and then switch the node design when a real reason appears.

What happens inside the computer

When you write TrieNode(), Python creates one object on the heap, which is the area of memory where objects live. The object holds a reference to a list, and the list holds 26 references. A reference is the address of another object, or None if there is nothing there. Python sets every slot to None for you when you write [None] * 26.

You can ask Python how many bytes an object takes with sys.getsizeof. It counts the object itself, not the objects it points to. Here are the results on one machine with Python 3.14. Your numbers will differ with the Python version and the computer.

The output on the machine used for this lesson was:

empty list: 56
list of 26 None: 264
empty dict: 64
dict with one key: 184

The list of 26 takes 264 bytes. That number is 56 bytes of list header plus 26 slots of 8 bytes each on a 64-bit Python. The dict with one key is bigger than an empty dict because it allocates space for its entries. A node object with its own two attributes takes about 48 bytes more on top of its list. On this machine that is about 312 bytes for each array node.

Suppose your words average 8 letters and you store 1,000 words with many shared prefixes. Each stored character can create at most one new node, so there are at most about 8,000 nodes. At about 312 bytes per node, that is about 2.5 MB, which is small. Real numbers depend on the machine, and they can be smaller because shared prefixes create fewer nodes than letters.

Design questions to answer before you code

Before you write a single line, answer five questions. Each answer changes the node design, and changing it later costs a rewrite.

1. What characters can appear? Lowercase letters only means 26 slots work. Capitals, digits or spaces mean you need a dict, or a mapping from characters to slot numbers. Python strings can hold any Unicode character, such as é or 中, and ord gives each one a number far above 25. A list of 26 cannot hold them. Asking this first avoids the index mistakes shown later in this lesson.
2. Can a word repeat? If it can, decide whether a repeat should change anything. For a set of words, it should not. For a count of occurrences, it should. The answer decides whether insert must check first.
3. Is the empty word allowed? If it is, the root must be able to hold the flag. If it is not, reject it at the door so it never reaches the trie.
4. Do you need prefix counts, or only yes and no? A set of words needs only the flag. Counts on each node add a field and an update to every insert, and they are worth it only when the problem asks for them.
5. How many words, and how long are they? A rough estimate tells you whether 26-slot nodes fit in memory. For a few thousand words, almost any design works. For millions of long words, the node design can decide whether the program fits in memory at all.

Write the answers as one line each at the top of your file. If a question has no answer, ask the person who gave you the problem before you guess.

The costs

Let L be the length of the word you are working with. For list children, inserting a word, searching for it and checking a prefix each take O(L) time. The notation O(L) means the time grows in proportion to L. It does not depend on how many words are stored. A set also costs O(L) to hash a string, but it cannot answer prefix questions at all.

The space is the number of nodes you create. In the worst case, every character of every word creates its own node, so the total is at most the sum of the word lengths plus one for the root. Shared prefixes make it smaller, and that is the reason tries are efficient for dictionaries with many words that begin the same way.

Here is what that means in practice. Suppose you store 100,000 words of average length 8, and a user types two letters. A plain list has to look at every word, so it can read up to 800,000 characters before it has an answer. A trie walks two nodes to reach the prefix, and then visits only the words below that node. The walk to the prefix costs the same whether the dictionary holds a thousand words or a million. The cost of the answer still grows with the number of matches you collect, but it never grows with the words that do not match. That difference is why a trie suits typing that has to feel instant.

Memory is the other side of the trade-off. The list design spends about 264 bytes on the slots of every node, and a node with a single child wastes 25 of its 26 slots. The dict design spends little on empty slots, but each step pays for a hash lookup. Neither design is always better. Choose the one that fits your alphabet and your data, and be ready to say why in one sentence.

Worked example 1: build a trie by hand

Store the four words to, tea, ten and in, in that order. Start with only the root.

1. Insert to. The root has no child for t, so create node t. Move to t. The t node has no o child, so create o under t. Move to o. The word ends here, so set the flag on o. Nodes so far: t, to. The flag is set on to.
2. Insert tea. From the root, t already exists, so reuse it. Under t, there is no e, so create te. Under te, there is no a, so create tea. Set the flag on tea. Nodes so far: t, to, te, tea.
3. Insert ten. Reuse t and te. Under te there is no n, so create ten. Set the flag on ten. Nodes so far: t, to, te, tea, ten.
4. Insert in. From the root there is no i, so create i. Under i there is no n, so create in. Set the flag on in. Nodes so far: t, to, te, tea, ten, i, in.

Count the nodes, not counting the root. You get seven. Each of those seven is the path to a distinct prefix: t, to, te, tea, ten, i, in. The letter t appears in three words, but it is stored once. The letters total 2 plus 3 plus 3 plus 2, which is 10, so the trie saves three nodes compared with storing every letter separately. The number seven is the answer you should get when you check your own tree, and it is also what the program in the next example prints.

Now look at the flags. to, tea, ten and in are word ends. t, te and i are not. If someone asks search("te"), the path exists but the flag is off, so the answer is False. If someone asks starts_with("te"), the path exists, so the answer is True. Those two questions have different answers on the same node, which is why both the flag and the path matter.

Worked example 2: count the nodes with a program

Here is a complete program that uses list children. It inserts the words into the trie and prints how many nodes exist. The counting method is recursion. A recursive function is one that calls itself on a smaller problem. To count the nodes under a node, you count the node itself and then count the nodes under each of its children. A child that is None contributes nothing.

The program prints:

nodes: 4

Look at the three parts of the program. The loop near the end calls insert once for each word in the list. insert is exactly the walk you did by hand in the example above. count_nodes is the recursive count. It starts at 1 for the node it was given, so the root contributes 1, and the final - 1 removes the root from the answer.

The list has car twice. The second car does not create anything new, because every node it needs already exists. The answer is 4, from the path c, a, r, e. You can predict that answer from the drawing before you run the program, and that is a good habit: predict first, then run.

The docstring, the line in triple quotes under def count_nodes, is a short note that Python stores with the function. Use it to say what a function does, as the comment in the Java version does.

Worked example 3: the index arithmetic

The line i = ord(ch) - ord("a") is the part beginners most often get wrong, so it deserves its own program. This one prints the index for each letter of a word.

The program prints:

t -> 19
r -> 17
i -> 8
e -> 4

Here is what happens for the first letter. ch is "t", and ord("t") is the number 116. ord("a") is 97. The subtraction gives 19. Slot 19 is the letter t, because a is slot 0, b is slot 1, and so on. Counting from the start of the alphabet gives 19 letters before t, so that is its index.

Now try Tea. The capital T has its own number, 84, which is smaller than the number for a:

The program prints:

T -> -13
e -> 4
a -> 0

The capital T gives -13. A list index should never be negative, and Python does not stop you from using one. It counts backward from the end of the list. Index -13 is the same as index 13 in a list of 26 items, so the T node is stored in slot 13, which is the letter n. The next program shows it.

The program prints:

filled slots: [13]

Slot 13 is n, not t, which is slot 19. No error was raised, so a bug like this is quiet. The "Common mistakes" section below shows a check that makes Python stop on this kind of mistake.

Worked example 4: search and starts_with, step by step

Use the trie from the first worked example, which holds to, tea, ten and in. Four queries show the two checks side by side. For each query, the table lists the slot index of each letter (computed as ord(ch) - ord("a")) and what the walk finds.

Read the tea row in order. The first letter is t, which is ord("t") - ord("a"), so index 19. The root's slot 19 holds the t node, so the walk moves there. The second letter is e, index 4. The t node's slot 4 holds the te node, so the walk moves there. The third letter is a, index 0, and the te node's slot 0 holds the tea node. The walk ends on tea. Its flag is on, so search says True. The path exists, so starts_with says True too.

The te row shows the difference between the two checks most clearly. The walk ends on the node that both tea and ten pass through, but te was never inserted as a word, so its flag is off. search needs the flag and says False. starts_with only needs the path and says True.

The ti row shows a walk that fails. The t node is found, but it has no child at slot 8, which is ord("i") - ord("a"). The walk returns nothing, and both checks say False. The stored word in starts with i, not ti, so nothing in the trie spells ti, and the failure is correct.

The next program writes the two checks as functions and runs the four queries.

The program prints:

tea True True
te False True
ti False False
ten True True

The walk function does the same steps as the table. It returns None when a slot is empty, and that single value tells search and starts_with what happened.

Worked example 5: counting nodes, call by call

The counting program from earlier works by recursion. Here is the call order for the trie of to, tea, ten and in. The loop in count_nodes visits slots from 0 to 25, so a node's children are visited in alphabetical order of their letters.

1. count_nodes(root) starts with a total of 1. Its children are at slots 8 (i) and 19 (t). Slot 8 comes first.
2. count_nodes(i) starts at 1. Its only child is in at slot 13. count_nodes(in) has no children, so it returns 1, and count_nodes(i) returns 2.
3. Back at the root, slot 19 holds t. count_nodes(t) starts at 1. Its children are te at slot 4 and to at slot 14. Slot 4 comes first.
4. count_nodes(te) starts at 1. Its children are tea at slot 0 and ten at slot 13. Both have no children, so each returns 1. count_nodes(te) returns 3.
5. Back at t, slot 14 holds to, which has no children and returns 1. So count_nodes(t) returns 1 + 3 + 1, which is 5.
6. The root returns 1 + 2 + 5, which is 8. The program prints 8 minus 1, so the answer is 7.

Count the calls too. There are eight calls, one for each node including the root. Each node gets exactly one call, because a node is reached through exactly one parent. So the recursion does work in proportion to the number of nodes, and the nodes are the very thing being counted. A walk that visits each node once is the cheapest possible count.

Common mistakes

Some mistakes show up again and again in trie code. Learn to recognise each one.

Using the character as the index. Writing cur.children[ch] for a letter ch is a mistake. A list index must be a whole number, and Python says so:

TypeError: list indices must be integers or slices, not str

The fix is ord(ch) - ord("a"). The other common version is writing cur.children[ord(ch)] without the subtraction. That gives an index near 97 for lowercase letters, and the list has only 26 slots, so Python raises an error:

IndexError: list index out of range

The message names the problem, but not the bad index. Look at the line the traceback points to, and print the index just before it if you are unsure.

Capital letters or spaces in a list trie. This is the Tea example from above. For a capital T, the index is -13. Python does not raise an error for a negative index on a read or a write inside range. Your insert quietly stores the T node under the wrong letter, as the earlier program showed. The walk for tea then fails, and the bug is hard to find. A check at the door prevents it:

def check_word(word):
    if not all("a" <= ch <= "z" for ch in word):
        raise ValueError(f"only lowercase a to z: {word!r}")

The fix is either to convert the input to lowercase with word.lower(), or to switch to dict children if the alphabet really includes capitals. Decide that when you design the node, not when the program misbehaves. The f"..." text is an f-string, which puts the value of word into the message. The !r part adds quotes around the value, so a space or a capital letter is easy to see. Run check_word("Tea") and it raises ValueError: only lowercase a to z: 'Tea'.

Forgetting the end-of-word flag. If you insert car and never set is_word on the r node, then search("car") returns False. It is an easy bug to miss, because the path is there and the output looks plausible. The debugging section below shows how to catch it.

Storing the whole word on every node. Some beginners put the full string on each node, such as "car" on the r node. That wastes memory and is not needed. The path already spells the word. Store the flag, and rebuild the string from the path when you need it, as the autocomplete code in a later lesson does.

Creating a child but not moving into it. A common insert bug is to create the child and then forget cur = cur.children[i]. The next character then goes under the wrong node. The trace in the first worked example shows the correct order: create the child, then move into it, then go on to the next character.

Mixing up a node and a letter. A node is an object with its own children and flag. A letter is just a number from 0 to 25 when you use a list, or a one-character string when you use a dict. Keep the two apart in your head. The index is the letter, and the object at that index is the node for the prefix ending in that letter.

Debugging walkthrough: printing the tree

A trie is hard to debug by looking at the code alone. A better tool is to print the whole tree, so you can compare what you see with the picture you expected. The next program does that. It inserts the words and prints one line per node, indented by depth. Each word-ending node gets a star. This version uses dict children, so the children can be sorted by letter with sorted.

The program prints:

root
  c
    a
      r *
      t *
  d
    o
      g *

Read it against the drawing from earlier. The c line sits under root, and the a line sits under c, so ca is a path. The r and t lines are word ends, so they have stars. The c and a lines have no star, so c and ca are not words. If a word were missing its flag, the star would be missing from its line. That is how you spot the bug in seconds.

Now a debugging exercise. Change the word list to ["ca"] and run it. The output is root, then c, then a *. The star is on a only, because only the path ca was inserted. Next, suppose you forget the line cur.is_word = True in insert. Run the program again with cat, car and dog. Every star disappears, and the tree still has the same shape. You can see at once that the structure is right and the flags are wrong, so the bug is in the flag code and not in the walk.

Variations and edge cases

Real problems bring details that the basic design does not cover. Think about these before you write any code.

The empty word. An empty string has no characters, so its path is the root itself. Inserting "" should set the flag on the root. Your code does this without special handling, because the loop does not run. Searching for "" then returns True only if you inserted it, which is usually the right answer. Check the problem statement, because some tasks say the empty word is never given.

Duplicates. Inserting the same word twice leaves the trie unchanged, which is correct for a set of words. But if you also keep a count of words under each node, duplicates will inflate it. The second lesson shows how to handle that.

Digits, capitals and punctuation. These need the dict design, or you must map each character to a smaller number before using the list. Do not assume your input is clean. Read the problem statement and decide.

Very long words. The cost of an operation grows with the word length. A trie with words of 10,000 characters still works, but each word can create up to 10,000 nodes, so memory grows fast. Python has a limit on how deep a recursive function may go, which is 1,000 calls by default. A recursive count over a word of 10,000 characters can reach that limit. The count_nodes function in this lesson recurses once per character of depth. On the machine used for this lesson, a single word of 900 a characters counts fine, and one of 1,100 fails with RecursionError: maximum recursion depth exceeded. The iterative version in the practice section does not have this limit.

One word that is the start of another. Storing car and card is the normal case. The flag on r is set, and d continues below it. Nothing special is needed, but it is the case that tests whether you understood the flag.

Interview-style questions and real uses

When an interviewer asks about tries, the first question is usually why you would use one instead of a set. A good answer is short. A set answers membership for whole words in about constant time for a fixed-size key. A trie answers membership in time proportional to the word length, and it also answers prefix questions, which a set cannot do without a full scan. If the question is only "is this exact word stored", the set is often simpler and just as fast.

Tries show up in several real systems. Autocomplete and search suggestions walk to a prefix node and list the words below it. Spell checkers use tries to test many dictionary words quickly. Phone keyboards that predict the next word use similar structures. Network routers need to find the longest matching address prefix, and they often use a related structure called a binary trie, which a later lesson of this module builds.

When you explain a trie in an interview, say three things: each edge is one character, a word is a path with its end flagged, and the cost of an operation depends on the word length. Those three points cover most follow-up questions.

Practice

1. Draw the trie for the words to, tea, ten and in. Mark each word end with a star. Hint: te is shared by tea and ten, and t is shared by all of the t words.

Show the answer: Start at the root. It has two children: t and i. Under t there is o* (for to), and t itself is not a word. Under t there is also e, which leads to te (not a word), then tea* and ten* as children of te. Under i there is n* for in, and i itself is not a word. The picture has seven nodes besides the root: t, to*, te, tea*, ten*, i, and in*.

2. How many nodes, not counting the root, does that trie have? Explain how you counted.

Show the answer: Seven. Each distinct prefix creates one node, and the distinct prefixes are t, to, te, tea, ten, i, and in. The letters in the four words total ten, but t and te are shared, so three letters are saved.

3. Explain in one sentence why search("te") returns False but starts_with("te") returns True on the same trie.

Show the answer: The node for te exists because tea and ten pass through it, so the path is there and starts_with is True. But te was never inserted as a word, so its end-of-word flag is off, and search returns False.

4. You want to store the word Hi in a list-based trie with 26 slots. What index does the program compute for H, and what goes wrong?

Show the answer: ord("H") - ord("a") is 72 - 97, which is -25. Python does not raise an error for a negative index inside the list's range. Index -25 is the same as slot 1, which is b, so the H node is stored under b and the trie is wrong without any message. Either lowercase the input first, or use a dict of children if capitals are real data.

5. Change the counting program so it prints the number of word ends instead of the number of nodes. What is the answer for to, tea, ten and in, and why does it not equal the node count?

Show the answer: Four. Each inserted word sets one flag, and the four words are to, tea, ten and in. The node count is larger because intermediate prefixes like t and te also become nodes, and they are not word ends.

6. Rewrite count_nodes without recursion, using a list as a stack (a last-in, first-out pile). Hint: start with the root in the list, pop a node, count it, push its non-empty children, and repeat until the list is empty.

Show the answer: Start with stack = [root] and a counter at 0. While stack is not empty, call node = stack.pop(), add 1 to the counter, and call stack.append(child) for each child that is not None. The loop counts each node exactly once. For the trie of to, tea, ten and in it returns 8, and the answer is 8 minus 1, which is 7, the same as the recursive version. This version has no depth limit, so it works for words of any length.

7. The dict-based node stores {} with one-character string keys. Explain why a plain string works as a key, even though a character in C or Java is a separate type.

Show the answer: Python has no separate character type. A one-character string such as "c" is a string, and two equal strings always produce the same hash, so a dict lookup with "c" finds the entry stored under "c". No conversion step is needed, which is why the dict code looks the same as a dict of any other keys.

8. Estimate the memory for a list-based trie built from 500 words that average 6 letters, with no sharing of prefixes at all. Use 312 bytes per node. Then say why real tries use less.

Show the answer: With no sharing, each letter creates a node: 500 times 6 is 3,000 nodes. At 312 bytes per node, that is about 936,000 bytes, or about 0.94 MB. Real word lists share many prefixes, such as s, st and sta, so the real count of nodes is smaller than 3,000. The number 312 is from one machine and one Python version, so your count will differ.

9. Predict the output of the debugging program if the word list is ["ca"]. Then explain what it shows about the flag.

Show the answer: The output is root, then c, then a *. Only a has a star, because only the path ca was inserted. The c line has no star, showing that the prefix c exists but is not a word.

What you now know

• A trie stores words as paths from the root, one character per edge, so shared beginnings share nodes.
• Each node has children and an end-of-word flag, and the flag is what separates a word from a prefix.
• List children are fast for the letters a to z. Dict children suit large or unknown alphabets.
• Insert, search and prefix checks each cost time proportional to the word length, not to the number of stored words.
• Printing the tree is the quickest way to find a missing flag or a wrong path.
• Watch for the index trap: ord(ch) - ord("a") must be between 0 and 25. Python does not stop a negative index, so capital letters need a check.

In the next lesson you will write the full set of operations (insert, search, starts_with and a count of words under a prefix) as one class.