Trie Operations: Insert, Search, and StartsWith

Welcome back! In our last lesson, we built a strong conceptual foundation for the Trie data structure. We explored its prefix-based structure, the critical role of the isEndOfWord flag, and most importantly, we established when a Trie is a more powerful tool than a hash map—specifically, for any task involving prefix lookups.

Today, we're moving from concept to code. This lesson is all about implementation. You will learn to implement the core insert, search, and startsWith operations for a standard Trie. By the end, you'll have a complete, working Trie class, a fundamental tool for tackling a variety of string-based problems in coding interviews and beyond.

The Building Blocks: TrieNode and Trie

Before we can implement the operations, we need to define the structure of the Trie itself. This involves two main components: the TrieNode class, which represents each character in our tree, and the Trie class, which will orchestrate the operations starting from a root node.

As we discussed, a TrieNode needs two things:

1. A way to point to its children (the next characters in a word).
2. A boolean flag to mark if the path to this node represents a complete word.

For the children, a common and efficient approach for a known, small character set like lowercase English letters is a fixed-size array. We can use an array of size 26, where index 0 corresponds to 'a', index 1 to 'b', and so on.

Here's a simple Python class definition for the TrieNode:

class TrieNode:
    def __init__(self):



        # children will store TrieNode objects
        self.children = [None] * 26 
        self.isEndOfWord = False

The main Trie class is even simpler to start. It just needs a root node, which is itself an empty TrieNode. All operations will begin from this root.

class Trie:
    def __init__(self):
        self.root = TrieNode()

This is a common pattern in tree-based data structures: a simple container class that holds the root and the methods to manipulate the structure.

The insert Operation

Now, let's implement the insert method. The goal is to add a word to our trie, creating new nodes as needed and reusing existing ones if a prefix already exists.

The process is an iterative traversal:

1. Start with a current_node pointer at self.root.
2. For each character in the input word:
   a. Calculate the character's index (e.g., index = ord(char) - ord('a')).
   b. Check if current_node.children[index] is None. If it is, this path doesn't exist yet, so we create a new TrieNode at that position.
   c. Update current_node to move down the tree: current_node = current_node.children[index].
3. After the loop finishes, current_node points to the node representing the last character of the word. We mark it as a complete word by setting current_node.isEndOfWord = True.

This image perfectly visualizes the insert process. Notice how for "trie", the 't', 'r', and 'e' nodes are added sequentially. When "algo" is added, a new branch is created from the root.

The following video provides a live walkthrough of coding the insert function.

The search and startsWith Operations

The logic for search and startsWith is very similar to insert: both involve traversing the trie character by character. The difference lies in what they do after the traversal.

To make our implementation clean and avoid repeating code—a good practice you'll recognize from your internship experience—we can create a helper method. Let's call it _search_prefix. This helper will take a word or prefix as input and traverse the trie. It will return the final node if the path exists, or None if the path is broken at any point.

# Helper method within the Trie class
def _search_prefix(self, word):
    current_node = self.root
    for char in word:
        index = ord(char) - ord('a')
        if current_node.children[index] is None:
            return None # Path does not exist
        current_node = current_node.children[index]
    return current_node # Path exists, return the final node

With this helper, search and startsWith become incredibly simple.

search(word)

To search for a complete word, we need two conditions to be met:

1. The entire path for the word must exist in the trie.
2. The final node on that path must be marked as the end of a word (isEndOfWord == True).

Using our helper:

def search(self, word: str) -> bool:
    final_node = self._search_prefix(word)



    # The word exists if the path was found AND it's marked as an end of a word.
    return final_node is not None and final_node.isEndOfWord

startsWith(prefix)

To check if any word starts with a given prefix, we only need to satisfy one condition:

1. The entire path for the prefix must exist in the trie.

We don't care if the final node is the end of a word or not.

Using our helper:

def startsWith(self, prefix: str) -> bool:
    final_node = self._search_prefix(prefix)



    # The prefix exists if the path was found.
    return final_node is not None

This clear separation of concerns is what makes the trie so elegant. The traversal logic is shared, and the specific operation is determined by the final check.

Complete Implementation and Analysis

Let's now assemble all the pieces into a complete Trie class. The following resource provides a clean, well-documented implementation that mirrors the LeetCode problem statement.

Conclusion

In this lesson, we transitioned from the theory of Tries to their practical implementation. You've now seen how to construct a Trie class from the ground up, complete with its core insert, search, and startsWith methods.

Key Takeaways:

• A Trie is typically implemented with a TrieNode class (for the nodes) and a Trie class (for the root and methods).
• The insert operation traverses the trie, creating new TrieNodes for characters not yet in the path, and marks the final node with isEndOfWord = True.
• The search operation traverses the trie and returns True only if the full path exists and the final node's isEndOfWord flag is true.
• The startsWith operation traverses the trie and returns True if the full path for the prefix exists, regardless of the isEndOfWord flag.
• All three core operations have a time complexity of $O(L)$, where $L$ is the length of the string, making them highly efficient.

You now have a solid grasp of how to build and use a standard Trie. This is a significant step, but the real power of a Trie becomes apparent when we combine it with other algorithms.

In the next lesson, we will do just that. We'll revisit backtracking and see how a Trie can be used to dramatically optimize a search for words on a 2D grid, a classic and challenging problem type (e.g., Word Search II).