Implementing a Trie Data Structure

Welcome to the next lesson in our module on high-value interview patterns. In our last session, we mastered the monotonic deque to solve the sliding window maximum problem, an efficient technique for handling array-based window queries. Today, we'll shift our focus from arrays to a specialized tree-like data structure designed for string manipulation: the Trie, also known as a Prefix Tree.

Many interview problems revolve around searching, validating, or organizing large sets of strings. A Trie provides an elegant and highly efficient way to handle these tasks. In this lesson, you will learn how to build a Trie from scratch and implement its three fundamental operations: inserting a word, performing an exact search for a word, and checking if any words start with a given prefix. This is a classic data structure that frequently appears in coding interviews, often as a building block for more complex problems.

What is a Trie?

Imagine organizing a dictionary. You wouldn't just have a single, unsorted list of words. You'd group them alphabetically. A Trie takes this idea and applies it character by character. It's a tree where each path from the root to a node represents a prefix. Shared prefixes (like "cat" in "caterpillar" and "catnap") are represented by a shared path, which makes Tries very space-efficient for datasets with many common prefixes.

A Trie has a few key characteristics:

• It starts with an empty root node that doesn't represent any character.
• Each node has children, where each child corresponds to a specific character.
• A special flag on each node indicates whether the path to that node forms a complete word.

This structure makes it exceptionally fast to look up words or prefixes. To get a clear visual and conceptual understanding of what a Trie is and why it's useful for applications like autocomplete, let's start with a short video from NeetCode.

The following diagram illustrates the core components of a Trie, including the node structure, which we'll implement next.

Implementing the Trie in TypeScript

To build a Trie, we first need to define the structure of its nodes. As you've seen, each node must keep track of its children and whether it marks the end of a word. Given your extensive experience with JavaScript and TypeScript, using a Map to store the children is the most idiomatic and flexible approach. It allows for any character to be a key, unlike a fixed-size array which is often limited to a specific character set (like 'a'-'z').

Let's look at a clean TypeScript implementation for the TrieNode.

The Trie class itself simply starts with a root property, initialized to a new, empty TrieNode. All operations will begin their traversal from this root.

Core Operations: insert, search, and startsWith

Now, let's implement the three core methods required by our learning outcome. The logic for all three involves traversing the Trie from the root, one character at a time.

1. insert(word)

To insert a word, we trace a path from the root. For each character in the word:

1. Check if the current node has a child corresponding to that character.
2. If it doesn't, create a new TrieNode and add it to the current node's children map.
3. Move the currentNode pointer to that child node.
4. After iterating through all characters, mark the final node's isEndOfWord property to true.

This image clearly illustrates the process. When "ant" is inserted after "and", the existing path for "an" is reused, and a new branch for 't' is created from the 'n' node.

The following reading provides the TypeScript implementation for this logic.

2. search(word)

Searching for an exact word is similar to inserting, but with a crucial final check. You traverse the Trie character by character. If you ever encounter a character for which a child node does not exist, you know the word isn't in the Trie and can immediately return false.

If you successfully traverse all characters of the word, you land on a final node. For an exact match, this node's isEndOfWord flag must be true. If it's false, it means the word is only a prefix of another word in the Trie (e.g., searching for "app" when only "apple" has been inserted). This distinction is a common source of bugs and a key point to master for interviews.

To drive this point home, it's worth reading about this common pitfall directly.

3. startsWith(prefix)

This method checks if there is any word in the Trie that begins with a given prefix. The implementation is nearly identical to search, but it's simpler. You traverse the Trie based on the characters in the prefix. If you can complete the traversal for the entire prefix, you return true. If at any point a character's node is missing, you return false.

Crucially, you do not need to check the isEndOfWord flag at the end. The mere existence of the path for the prefix is sufficient.

Complexity Analysis

The reason Tries are so powerful is their performance characteristics.

• Time Complexity: For insert, search, and startsWith, the time complexity is $O(L)$, where $L$ is the length of the word or prefix. The runtime depends only on the length of the string being processed, not on the total number of words in the Trie. This is a significant advantage over, for example, searching in an unsorted list of strings, which would be $O(N\cdot L)$, where N is the number of words.
• Space Complexity: The space complexity is proportional to the total number of characters in all words stored, but shared prefixes reduce the total number of nodes. In the worst case (no shared prefixes), it's $O(\text{total characters})$.

The DEV.to article provides a concise summary of this.

Conclusion

In this lesson, you have learned to build and use one of the most important string-related data structures in the algorithmic toolkit. A Trie is the go-to solution for problems requiring efficient prefix matching and dictionary-style lookups.

Here are the key takeaways:

• A Trie (Prefix Tree) is a tree structure where paths from the root represent strings, and common prefixes are shared.
• A TrieNode typically contains a children collection (a Map is ideal in TypeScript/JavaScript) and an isEndOfWord boolean flag.
• Insertion involves traversing the Trie and creating new nodes as needed, finishing by setting isEndOfWord = true on the final node.
• Exact search requires a full traversal and a check that isEndOfWord is true on the final node.
• Prefix search requires only a full traversal of the prefix characters; the isEndOfWord flag is irrelevant.
• All three core operations have a time complexity of $O(L)$, where $L$ is the length of the input string.

In our next lesson, we will explore multi-source Breadth-First Search, a powerful graph traversal technique used to model problems involving simultaneous expansion from multiple starting points, such as finding the nearest gate in a grid or tracking the spread of a forest fire.