Implementing Tries

1. What is a Trie?

A Trie is a tree-like data structure where each node stores a character. By traversing from the root down a path of nodes, you can spell out a word or a prefix. A key feature is that words with common prefixes share the same initial path in the tree, making it highly memory-efficient for storing large dictionaries.

Imagine you want to store the words "and", "ant", "dad", and "do". A Trie would organize them like this:

2. The Structure of a Trie Node

To build a Trie, we first need to define the structure of its nodes. Since we are focusing on interview and competitive programming contexts, we'll assume words consist of only lowercase English letters ('a' through 'z').

Each node in our Trie needs two key pieces of information:

1. An array of children nodes: Since there are 26 possible lowercase letters, each node will have an array of 26 pointers to other TrieNodes. The pointer at index 0 will correspond to the character 'a', index 1 to 'b', and so on. We can easily find the index for a character c with the expression c - 'a'.
2. A boolean flag: We need a way to know if a path from the root to the current node represents a complete word that was inserted, or just a prefix. A flag, let's call it isEndOfWord, serves this purpose.

Here's how we can represent this TrieNode in Java. We'll define it as a static inner class within our main Trie class for encapsulation.

class Trie {

    static class TrieNode {
        TrieNode[] children;
        boolean isEndOfWord;

        public TrieNode() {
            children = new TrieNode[26]; // For 'a' through 'z'
            isEndOfWord = false;
        }
    }

    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // We will implement insert(), search(), and startsWith() here.
}

3. Visualizing the Core Operations

Before we jump into coding, let's build a strong mental model of how insert, search, and startsWith work. The following video provides an excellent walkthrough of these operations.

4. Implementing the Trie in Java

Now, let's translate the concepts from the video into a practical Java implementation. We will implement three core methods: insert, search, and startsWith. While the learning outcome focuses on insert and search, startsWith is fundamental to a Trie's purpose and is a natural extension we'll need for our next lesson.

The following resource provides a clean, well-explained Java implementation that is very close to what you'd be expected to write in a technical interview.

Let's break down the logic for each method based on that implementation.

Insertion (insert)

To insert a word, we traverse the Trie from the root, character by character.

1. Start with a currentNode pointer at the root.
2. For each char in the word:
   • Calculate its index (char - 'a').
   • If currentNode.children[index] is null, it means this path doesn't exist yet. Create a new TrieNode at that position: currentNode.children[index] = new TrieNode();.
   • Move the currentNode to its child: currentNode = currentNode.children[index];.
3. After the loop finishes, the currentNode is at the node corresponding to the last character of the word. Mark it as the end of a word: currentNode.isEndOfWord = true;.

// Inside the Trie class
public void insert(String word) {
    TrieNode currentNode = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (currentNode.children[index] == null) {
            currentNode.children[index] = new TrieNode();
        }
        currentNode = currentNode.children[index];
    }
    currentNode.isEndOfWord = true;
}

Search (search and startsWith)

Both search and startsWith involve traversing the Trie. We can create a private helper method, searchPrefix, to handle this traversal, which makes our code cleaner and avoids repetition. This helper will return the node at the end of the prefix, or null if the prefix doesn't exist.

Helper Method: searchPrefix

// Inside the Trie class
private TrieNode searchPrefix(String word) {
    TrieNode currentNode = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (currentNode.children[index] == null) {
            return null; // Path does not exist
        }
        currentNode = currentNode.children[index];
    }
    return currentNode; // Return the node at the end of the path
}

Now, search and startsWith become very simple.

• search(String word): For a word to exist, its entire path must exist, and the final node must be marked as the end of a word.

  public boolean search(String word) {
      TrieNode node = searchPrefix(word);
      return node != null && node.isEndOfWord;
  }
  

• startsWith(String prefix): For a prefix to exist, its entire path must simply exist. We don't care about the isEndOfWord flag.

  public boolean startsWith(String prefix) {
      TrieNode node = searchPrefix(prefix);
      return node != null;
  }
  

5. Complexity Analysis

Understanding the performance of a Trie is crucial for knowing when to use it.

• Time Complexity:

  • insert(word): $O(L)$, where $L$ is the length of the word. We iterate through the word once.
  • search(word): $O(L)$, where $L$ is the length of the word. We traverse a path of length $L$.
  • startsWith(prefix): $O(P)$, where $P$ is the length of the prefix.

• Space Complexity:

  • The space complexity is $O(N\cdot L_{avg})$, where $N$ is the number of words and $L_{avg}$ is the average length of a word. However, because prefixes are shared, the actual space is closer to $O(\text{total characters in all unique words})$. Each node takes up constant space (an array of 26 pointers and a boolean).

Conclusion

In this lesson, you've learned how to implement one of the most important string-based data structures. The Trie's ability to efficiently handle prefix-based queries makes it a go-to solution for many problems you'll encounter in interviews and competitive programming.

Key Takeaways:

• A Trie is a tree where paths from the root represent prefixes and words.
• Each Trie node contains an array of children (e.g., size 26 for lowercase letters) and a boolean flag (isEndOfWord) to mark the end of a complete word.
• The insert, search, and startsWith operations all have a time complexity linear in the length of the input string, which is highly efficient.
• Reusing code with helper methods (like searchPrefix) is good practice for cleaner and more maintainable implementations.

Preview of the Next Lesson:
Now that we have a fully functional Trie, we can start applying it to solve real problems. In our next lesson, we will implement a word search and autocomplete feature using a Trie. This will build directly on the insert and startsWith methods we've just created, showing you a practical and powerful application of this data structure.