Complete Guide to Trie Data Structure

Introduction

A Trie (pronounced "try"), also known as a prefix tree or digital tree, is a specialized tree-based data structure used primarily for efficient storage and retrieval of strings. The name "Trie" comes from the word "retrieval," highlighting its primary use case.

Tries are particularly powerful for problems involving string matching, prefix searching, and autocomplete functionality. Unlike binary search trees that compare entire keys, tries leverage the structure of strings by storing characters at each node.

What is a Trie?

A Trie is a tree data structure where:

• Each node represents a single character of a string
• The path from root to a node represents a prefix
• The path from root to a leaf (or marked end node) represents a complete word
• Each node can have multiple children, typically one for each possible character

Visual Example

Consider storing the words: "cat", "car", "card", "dog", "door"

        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t   r    g
        |    |
        d    o
             |
             r

Structure and Properties

Node Structure

Each Trie node typically contains:

1. Children: An array or hash map of child nodes (one for each possible character)
2. IsEndOfWord: A boolean flag indicating if this node marks the end of a valid word
3. Optional: Additional data like frequency count, word meaning, etc.

Key Properties

1. Root is empty: The root node doesn't store any character
2. Shared prefixes: Words with common prefixes share the same path
3. One path per word: Each complete word has exactly one path from root to an end node
4. No key collision: Unlike hash tables, tries don't have collision issues
5. Alphabetically ordered: Children can be stored in alphabetical order

Basic Operations

1. Insertion

Process:

• Start at the root
• For each character in the word:
  • If the character exists as a child, move to that child
  • If not, create a new node for that character
• Mark the last node as end of word

Example: Inserting "cat"

Step 1: root -> create 'c'
Step 2: 'c' -> create 'a'
Step 3: 'a' -> create 't', mark as end

2. Search

Process:

• Start at the root
• For each character in the word:
  • If the character exists as a child, move to that child
  • If not, return false
• After traversing all characters, check if current node is marked as end of word

3. StartsWith (Prefix Search)

Process:

• Similar to search
• But only need to verify all characters exist
• Don't need to check if it's an end of word

4. Deletion

Process:

• Find the word in the trie
• Remove nodes from bottom to top, but only if:
  • The node has no other children
  • The node is not marking end of another word
• Use recursion for clean implementation

Implementation

class TrieNode {
  Map<Character, TrieNode> children;
  boolean isEndOfWord;

  public TrieNode() {
      children = new HashMap<>();
      isEndOfWord = false;
  }
}

class Trie {
  private TrieNode root;

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

  public void insert(String word) {
      TrieNode node = root;
      for (char c : word.toCharArray()) {
          node.children.putIfAbsent(c, new TrieNode());
          node = node.children.get(c);
      }
      node.isEndOfWord = true;
  }

  public boolean search(String word) {
      TrieNode node = root;
      for (char c : word.toCharArray()) {
          if (!node.children.containsKey(c)) {
              return false;
          }
          node = node.children.get(c);
      }
      return node.isEndOfWord;
  }

  public boolean startsWith(String prefix) {
      TrieNode node = root;
      for (char c : prefix.toCharArray()) {
          if (!node.children.containsKey(c)) {
              return false;
          }
          node = node.children.get(c);
      }
      return true;
  }
}

Time and Space Complexity

Time Complexity

Space Complexity

• Worst case: O(ALPHABET_SIZE × N × M)

  • ALPHABET_SIZE: Number of possible characters (26 for lowercase letters)
  • N: Number of words
  • M: Average length of words

• Best case: O(N × M) when words share many prefixes

• Practical: Much better than worst case due to prefix sharing

Applications

Advantages and Disadvantages

Advantages

1. Fast prefix search: O(m) time where m is prefix length
2. No hash collisions: Unlike hash tables
3. Alphabetical ordering: Can retrieve keys in sorted order
4. Memory efficient: For large datasets with common prefixes
5. Predictable performance: No worst-case hash collisions

Disadvantages

1. Memory intensive: Can use more memory than hash tables for small datasets
2. Cache performance: Poor cache locality due to pointer-heavy structure
3. Implementation complexity: More complex than arrays or hash tables
4. Not suitable for dense data: Best for sparse string datasets

Must-Do LeetCode Problems

Beginner Level

Why Problem #1 is Critical: This is the foundation for all trie problems. You must master this before attempting any other trie question.

Intermediate Level

Why Problem #4 is Critical: This is one of the most common trie questions in technical interviews. It combines trie with backtracking and is excellent for demonstrating optimization skills.

Advanced Level

Why Problem #7 is Critical: Introduces binary trie concept, which is essential for XOR-related problems. This pattern appears frequently in competitive programming.

Expert Level

Common Patterns

Pattern 1: Basic Trie with DFS

Used in: Word Search II, Design Add and Search Words

def dfs(node, path):
    if node.is_end:
        results.append(path)
    for char, child in node.children.items():
        dfs(child, path + char)

Pattern 2: Binary Trie for XOR

Used in: Maximum XOR problems

class BinaryTrieNode:
    def __init__(self):
        self.children = [None, None]  # 0 and 1

def insert_binary(root, num):
    node = root
    for i in range(31, -1, -1):
        bit = (num >> i) & 1
        if not node.children[bit]:
            node.children[bit] = BinaryTrieNode()
        node = node.children[bit]

Pattern 3: Trie with Additional Data

Used in: Map Sum Pairs, Autocomplete Systems

class TrieNode:
    def __init__(self):
        self.children = {}
        self.value = 0  # Additional data
        self.suggestions = []  # Additional data
        self.frequency = 0  # Additional data

Problem Priority Guide

If you only have time for a few problems, focus on these in order:

1. #208 - Implement Trie (Must do - foundation)
2. #212 - Word Search II (Most common in interviews)
3. #421 - Maximum XOR (Learn binary trie pattern)
4. #211 - Add and Search Words (Wildcard matching)
5. #1268 - Search Suggestions (Real-world application)

Conclusion

Mastering tries requires understanding both the data structure itself and the problems it solves best. Start with the basic implementation, progress through the must-do problems, and focus on recognizing when a trie is the right tool for the job.

The problems marked with ⭐⭐⭐⭐⭐ and ⭐⭐⭐⭐ are particularly important for technical interviews. Remember that trie problems often combine multiple concepts (DFS, backtracking, bit manipulation), so practice integrating these skills.

Additional Resources

• LeetCode Trie Tag
• Visualgo Trie Visualization
• Pattern Recognition: Most trie problems fall into 3 categories:
  • String prefix/suffix matching
  • Word search optimization
  • Binary/XOR operations