Tries

Build prefix trees for dictionary lookup, autocomplete, and prefix queries.

Est. 75 min Updated Suggest a fix
💡 Note
Prerequisites: trees, pointers, arrays, and strings. This implementation deliberately supports lowercase English letters a–z; define a different alphabet and input policy for other text.

Objectives: share work between common prefixes

A trie (pronounced “try”) is a rooted tree in which each edge represents one character. A path from the root spells a prefix, and a marker on a node says whether that path is a complete stored word. Words such as car, card, and care reuse their common car path. This makes lookup proportional to query length rather than the number of stored words, at the cost of memory for child links.

🎯 Pro Tip
Tries appear in autocomplete, prefix filtering, and dictionary lookups. The recently added Interview Problem-Solving Patterns → unit covers interview-style application and dry runs; this lesson focuses on the structure and its operations.

1. Node model and representation trade-offs

For a fixed alphabet of 26 lowercase letters, each node can hold 26 child pointers and a Boolean terminal flag. The edge for letter c is stored at index c−'a'. A terminal flag is necessary because both car and card can exist: the node for car is a word and also has a child. Without the flag, a prefix and a complete key become indistinguishable.

Trie node, initialization, and validated index · C
#include <stdbool.h>
#include <stdlib.h>

#define ALPHABET 26

typedef struct TrieNode {
    struct TrieNode *child[ALPHABET];
    bool is_word;
} TrieNode;

TrieNode *trie_node_create(void) {
    return calloc(1, sizeof(TrieNode));
}

int letter_index(char ch) {
    if (ch < 'a' || ch > 'z') return -1;
    return ch - 'a';
}

Zero-initializing with calloc sets children to null and is_word to false. An array representation is fast and simple, but every node reserves space for all 26 links even if it has one child. A map or sorted edge list saves memory for sparse nodes, but adds lookup overhead. Choose from expected alphabet size, word count, and memory constraints.

2. Insert a word

Start at the root and follow or create one edge per character. Mark the final node as a word. Inserting a word that is already present is idempotent: it ends by setting a flag that is already true. Empty strings can be represented by marking the root itself terminal, if the application allows them.

Insert lowercase words; failure leaves a valid partial trie · C
bool trie_insert(TrieNode *root, const char *word) {
    if (root == NULL || word == NULL) return false;
    TrieNode *node = root;
    for (size_t i = 0; word[i] != '\0'; i++) {
        int index = letter_index(word[i]);
        if (index < 0) return false;
        if (node->child[index] == NULL) {
            node->child[index] = trie_node_create();
            if (node->child[index] == NULL) return false;
        }
        node = node->child[index];
    }
    node->is_word = true;
    return true;
}

If allocation fails after part of a path is created, the trie remains structurally valid but may contain nonterminal prefix nodes. Retrying insertion can complete it. If atomic insertion is required, allocate the missing path separately and attach it only after every allocation succeeds. The exact memory-failure guarantee belongs in the API contract.

3. Search words and prefixes

A word search must reach the final node and see is_word. A prefix search only needs to reach the final node, even if it is not terminal. This difference is a frequent source of errors. For example, after inserting card, the query car is a valid prefix, but it is a stored word only if it was inserted separately.

Exact lookup and prefix lookup · C
TrieNode *trie_walk(TrieNode *root, const char *text) {
    if (root == NULL || text == NULL) return NULL;
    TrieNode *node = root;
    for (size_t i = 0; text[i] != '\0'; i++) {
        int index = letter_index(text[i]);
        if (index < 0 || node->child[index] == NULL) return NULL;
        node = node->child[index];
    }
    return node;
}

bool trie_contains(TrieNode *root, const char *word) {
    TrieNode *node = trie_walk(root, word);
    return node != NULL && node->is_word;
}

bool trie_has_prefix(TrieNode *root, const char *prefix) {
    return trie_walk(root, prefix) != NULL;
}

Both lookup operations take O(L) time for a query of length L. They do not scan every stored word. This complexity assumes indexing into a child array is O(1); map-based children may have different costs. An empty prefix reaches the root, so it is present whenever the root exists, even when no words are stored.

4. Autocomplete and delete semantics

Autocomplete first walks to the prefix node, then performs a DFS below it, adding characters to a working buffer and emitting words when a terminal node is reached. To cap results at k, stop after k matches; to return results in alphabetical order, visit child indices from 0 to 25. Listing all matches necessarily costs at least the number of characters emitted. Deletion clears the terminal flag; it should prune a node only if it is nonterminal and has no children, otherwise another word still depends on that path.

OperationWorkImportant condition
Insert / exact searchO(L)Every character must fit the chosen alphabet
Prefix lookupO(L)The path may exist without being a complete word
Enumerate suggestionsO(L + output size)Bound results to control latency and memory
SpaceO(total nodes × alphabet)Array child pointers may be wasteful for sparse tries
📌 Real World Example
A delivery app can use a trie to suggest neighbourhoods as someone types. Real systems also need ranking, locale-aware text normalization, result limits, and protection against very long or adversarial inputs; the bare trie solves prefix retrieval, not those product concerns.

5. Free every allocated node

Each created node owns all descendants reachable from it. A postorder traversal frees children before the parent. Call it once on the root when the complete dictionary is no longer needed; never free a child separately and then traverse it again from the root.

Postorder destruction · C
void trie_destroy(TrieNode *node) {
    if (node == NULL) return;
    for (int i = 0; i < ALPHABET; i++)
        trie_destroy(node->child[i]);
    free(node);
}

The recursive version is clear for ordinary word depths. If inputs can contain extremely long strings, recursion depth itself becomes a resource concern; use an explicit stack or a bounded input policy. In a long-running service, also consider whether the entire vocabulary fits in memory and how updates are published safely to readers.

6. Capacity planning and text policy

A trie’s node count depends on the number of distinct prefixes, not simply the number of words. If a million words share a long prefix, that prefix is stored once; if the words diverge immediately, many branches are needed. A fixed child array allocates 26 pointers for every node, including leaves. For a large dictionary, measure node count and memory before choosing this representation, and consider a compact edge vector, radix/compressed trie, or memory-mapped static index.

Text policy is part of correctness. This lesson treats input as lowercase single-byte English letters. To support case-insensitive search, normalize before insertion and lookup using the same rules. To support Unicode, code points or grapheme clusters need a deliberate encoding and normalization strategy; a byte-by-byte trie can split a multibyte character and does not automatically implement human-language prefix semantics.

⚠️ Important
Limit word length and request size in services that accept user input. A logically correct trie can still use unbounded memory or recursion depth when an attacker supplies extremely long strings.

7. Common mistakes

  • Confusing a prefix with a stored key: exact search checks the terminal marker; prefix search does not.
  • Forgetting to validate characters: indexing ch - 'a' without checking bounds can read or write outside the child array.
  • Assuming tries are always smaller or faster: a dense child array can consume far more memory than the raw words; benchmark the actual alphabet and workload.
  • Deleting shared paths: clear the terminal marker and prune only nodes that have no children and are not another word.

8. Practice

  1. Insert car, card, and care. Trace the shared path and answer exact-word and prefix queries.
  2. Implement a recursive suggestion collector that writes at most k lowercase words into a caller-provided result buffer.
  3. Implement deletion and explain why deleting car must not erase the path needed by card.
  4. Extend the input alphabet to digits as well as letters. Update the index function and memory analysis.
  5. Compare a trie to sorting a word array and binary-searching prefixes. Which workload makes each design attractive?

🎯 Key Takeaways

  • ✓A trie stores shared prefixes as shared paths in a rooted tree.
  • ✓A terminal marker distinguishes a complete word from a prefix.
  • ✓Insert and lookup take O(L) time for input length L under fixed-array child access.
  • ✓Alphabet design affects validation, lookup, and memory per node.
  • ✓Autocomplete cost includes enumerating and returning the results.
  • ✓Use the Interview Problem-Solving Patterns unit for separate interview-oriented practice.

Next

Track connected components efficiently as undirected edges are added.

Lesson 18 · Union-Find (Disjoint Set Union) →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...