Introduction to Trie

1. Why a Trie Is Needed

Suppose many words such as "cat", "car", "cap", and "dog" need to be stored. If they are kept as separate full words in a list, checking prefixes can become clumsy because each word may need to be inspected one by one.

The helpful observation is that many words share starting characters. A Trie uses this property by storing the common beginning once and branching only when the words become different. So "cat", "car", and "cap" can all reuse the same "ca" path before splitting at the last character.

Key Points

• Trie is most useful when prefix-based questions are frequent.

• Shared beginnings such as "app" in "app", "apple", and "apply" naturally fit the structure.

• Trie does not store words as one block; it builds them through paths of characters.

Algorithm

• Initialize an empty root node as the starting point for all words.

• Read each word from left to right so prefixes can be discovered naturally.

• Reuse an existing path while the same characters already exist in the Trie.

• Create a new branch only when the next required character is missing.

• Mark the final character of every complete word so prefixes and full words can be separated.

Complexity Analysis

Time Complexity: O(L), where L is the length of one word, because each character is processed once.

Space Complexity: O(L) in the worst case for one inserted word, because every character may need a new node if no prefix is shared.

2. Trie Structure: Root, Children, and End Marker

A Trie starts with an empty root node. From the root, each edge represents a character, and moving along a path builds a prefix. For example, the path root -> a -> p -> p forms "app".

The key detail is the end marker. A node may simply be part of a prefix, or it may mark the end of a complete word. This is how a Trie can know that "app" is a full word in one case, but only the beginning of "apple" in another.

Key Points

• The root usually represents an empty string.

• Each node keeps links to possible next characters.

• An end-of-word marker tells whether a complete word finishes at that node.

• A node can be both a word ending and the start of a longer word.

Algorithm

• Create a root node that does not store any character as a word by itself.

• Store child links from each node to the next possible characters.

• Move downward through child links to form prefixes.

• Mark a node when a complete inserted word ends there.

• Leave unmarked nodes as prefix checkpoints when no complete word ends at that position.

Complexity Analysis

Time Complexity: O(L) to build or follow the path for a word of length L, because one character is handled at each level.

Space Complexity: O(L) in the worst case for a new word, because a new node may be created for every character.

3. Inserting Words into a Trie

Insertion means adding a word into the Trie one character at a time. If the needed character path already exists, it is reused. If a character is missing, a new node is created for that character.

The intuition comes from shared prefixes. While inserting "apply" after "apple", the path a -> p -> p -> l already exists, so only the part where the word becomes different needs attention. The final node is then marked to show that the complete word is stored.

Key Points

• Insertion always starts from the root.

• Existing prefix paths should be reused.

• New nodes are added only for missing characters.

• The final node must be marked, otherwise the Trie may only remember the path as a prefix.

Algorithm

• Start at the root node so the word can be inserted from its first character.

• Check each character from left to right to follow the natural order of the word.

• Move to the existing child if the character path is already present.

• Create a new child node if the character path is missing.

• Continue until the last character is reached.

• Mark the final node as a complete word ending so future searches can recognize the inserted word.

Complexity Analysis

Time Complexity: O(L), where L is the length of the word being inserted, because each character is visited once.

Space Complexity: O(L) in the worst case, because a completely new word with no shared prefix may create L new nodes.

4. Searching for a Complete Word

Searching checks whether a full word has been inserted into the Trie. The path is followed character by character from the root. If a required character is missing, the word is not present.

The important property is that a path alone is not always enough. If "apple" was inserted, the path for "app" exists, but "app" should be treated as a complete word only if the node for the second p has an end marker.

Key Points

• A missing character immediately means the word is not present.

• A complete path without an end marker means the query is only a prefix.

• This distinction is the most common beginner confusion in Trie problems.

Algorithm

• Start at the root node.

• Read the search word from left to right.

• Move to the matching child for the current character.

• Return false if the required child does not exist, because the word path is broken.

• After all characters are processed, check the end marker on the final node.

• Return true only when the final node is marked as a complete word ending.

Complexity Analysis

Time Complexity: O(L), where L is the length of the searched word, because each character is checked once.

Space Complexity: O(1), because the search only needs a current node pointer while moving through the Trie.

5. Prefix Search and Autocomplete

Prefix search asks whether at least one stored word begins with a given prefix. This is slightly different from full-word search because the prefix does not need to be marked as a complete word.

The intuition is simple: if the path for the prefix exists, then the subtree below that path contains all possible continuations. That is why Trie feels natural for autocomplete. Once the path for "car" is reached, words like "car", "card", "care", and "careful" can be found below it.

Key Points

• Prefix search does not require an end-of-word marker at the final prefix node.

• Full-word search and prefix search follow the same path, but they answer different questions.

• Autocomplete usually starts with prefix search, then explores the subtree below the prefix node.

Algorithm

• Start at the root node.

• Read the prefix from left to right.

• Move to the matching child for each character.

• Return false if any required character path is missing.

• Return true after all prefix characters are consumed, because the prefix path exists.

• Explore the subtree below that final prefix node if actual autocomplete suggestions are needed.

Complexity Analysis

Time Complexity: O(P) to check a prefix of length P, because each prefix character is processed once. Listing suggestions takes additional time based on how many matching words are collected.

Space Complexity: O(1) for checking prefix existence, excluding the output list used when autocomplete suggestions are collected.

6. When Trie Is Worth Choosing

Trie is worth choosing when a problem repeatedly asks about prefixes, dictionary-style lookup, or grouped string exploration. It is not just a storage structure; it is a way to organize words so their common beginnings become easy to reuse.

The tradeoff is memory. A basic Trie can create many nodes, and each node may keep multiple child links. So a Trie is strongest when fast prefix queries matter enough to justify the extra structure.

Key Points

• Trie is a strong fit for autocomplete, spell checking, contact search, word games, and longest-prefix matching.

• Hash sets are often simpler for only checking whether full words exist.

• Trie becomes more useful when prefix queries are common.

• For large alphabets, child maps can save memory compared with fixed-size child arrays.

Key Takeaways

• Trie is a tree-like data structure for storing strings through character paths.

• It is also called a prefix tree because every path from the root forms a prefix.

• Shared prefixes are reused, which makes Trie powerful for prefix-based search.

• The end-of-word marker separates a complete word from a partial prefix.

• Insert, search, and prefix search usually take time proportional to the word or prefix length.

• Trie is excellent for autocomplete and dictionary-style tasks, but it can use more memory than simpler structures.