L20. Trie Data Structure & Implementation

A Trie (pronounced "try", derived from "retrieval"), also known as a Prefix Tree or Digital Tree, is an efficient, tree-like data structure used to store and retrieve a dynamic set of strings. Unlike binary search trees or hash tables, keys in a Trie are typically strings, and a node's position within the tree defines its associated key. Tries provide optimal time complexity for prefix-based operations, making them the industry standard for search auto-completion, spell checking, and network routing.

1. Why Do We Need a Trie? (The Problem Statement)

To understand why Tries exist, consider searching for words with a common prefix in standard data structures:

• Array / List of Strings: Finding all words starting with prefix "ca" requires scanning every string in the list.
  • Time Complexity: $O(N \times L)$, where $N$ is the number of words and $L$ is the average string length.
• Hash Map / Hash Set: Direct lookups for an exact match are fast ($O(L)$), but hash tables cannot perform prefix matching efficiently because hash functions destroy the ordering and prefix relationships between strings.
• Trie (Prefix Tree): Locates all words matching a prefix directly by traversing character-by-character along common path branches.
  • Time Complexity: $O(L)$ for search, insertion, and prefix verification, completely independent of the total number of stored words $N$.

Real-World Applications

1. Search Engine Autocomplete: As you type "CA" into Google, a Trie locates the "CA" node and instantly traverses descendant paths to suggest "cat", "car", and "cart".
2. Spell Checkers: Validates whether a typed string exists along a valid path and suggests corrections by exploring neighboring character nodes.
3. IP Routing (Longest Prefix Matching): Routers store destination subnets in binary Tries to match incoming packet IP addresses to target interfaces in constant time.

2. Core Mental Model & Structural Mechanics

Real-Life Analogy

Imagine walking through a multi-story physical dictionary where each floor is designated by a letter ('a' through 'z'). To find the word "car", you enter the building at the Root, take the elevator to the 'c' section, follow a hallway to the 'a' door, and finally enter the 'r' room. The final room contains a physical mark confirming that "car" is a complete word. If you continue walking into the adjacent 't' room, you find another mark for "cart".

Structural Properties

• Root Node: Represents an empty string "" and acts as the entry point for all operations.
• Nodes: Store references (pointers) to child character nodes.
• Edges: Represent individual characters connecting parent nodes to child nodes.
• Terminal Flag (isEnd): A boolean indicator marking whether the path from the root to the current node constitutes a complete, valid word.

Vertical Flow Architecture

Below is the vertical layout of a Trie populated with the words: "cat", "car", "cart", "do", and "dog".

3. Trie Node Architecture & Representation

For standard lowercase English alphabets ('a' through 'z'), each node maintains an array of size 26 containing references to its potential child nodes.

Node Data Structure

class TrieNode {
    // Array storing references to child TrieNodes (size 26 for 'a'-'z')
    TrieNode[] children;
    
    // Flag indicating if the path ending at this node forms a full word
    boolean isEnd;
    
    // Optional field: Stores the complete word string at terminal nodes
    // (Used to simplify DFS auto-complete / suggestion retrieval)
    String word;

    public TrieNode() {
        this.children = new TrieNode[26];
        this.isEnd = false;
        this.word = "";
    }
}

Index Calculation Formula

To convert any lowercase ASCII character into its corresponding array index:

Conceptually: Subtracting the ASCII value of 'a' (97) re-indexes character 'a' to 0, 'b' to 1, and 'z' to 25.

4. Operation 1: Word Insertion (insert)

Insertion builds the path for a word character-by-character. If a character node already exists, the algorithm reuses it; if not, it allocates a new TrieNode.

Step-by-Step Logic

1. Initialize an iteration pointer curr at root.
2. Iterate through each character ch in the target word.
3. Compute index = ch - 'a'.
4. Check if curr.children[index] is null:
   • If null, create a new TrieNode at curr.children[index].
5. Move curr pointer to curr.children[index].
6. Once the character loop completes, set curr.isEnd = true.

Java Implementation

public void insert(String word) {
    TrieNode curr = root;
    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        // Allocate a new node if the path does not exist
        if (curr.children[index] == null) {
            curr.children[index] = new TrieNode();
        }
        // Advance pointer to child node
        curr = curr.children[index];
    }
    // Mark the final node as a valid complete word
    curr.isEnd = true;
}

5. Operation 2: Full Word Search (search)

Searching verifies whether a given word was previously inserted into the Trie as a complete word.

Step-by-Step Logic

1. Start at curr = root.
2. Traverse through each character ch in the input word.
3. Compute index = ch - 'a'.
4. If curr.children[index] is null, return false (the path breaks, word does not exist).
5. Otherwise, advance curr to curr.children[index].
6. After processing all characters, return curr.isEnd.

Key Distinction: Returning true requires both character path completion AND curr.isEnd == true. If the character path exists but isEnd is false, the search string is merely a prefix, not a full word.

Dry-Run Example

• Search "car" in Trie containing "cart":
  • 'c' exists $\rightarrow$ 'a' exists $\rightarrow$ 'r' exists.
  • Node 'r' has isEnd == true. Return true.
• Search "ca" in Trie containing "cart":
  • 'c' exists $\rightarrow$ 'a' exists.
  • Node 'a' has isEnd == false. Return false.

Java Implementation

public boolean search(String word) {
    TrieNode curr = root;
    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (curr.children[index] == null) {
            return false; // Character branch missing
        }
        curr = curr.children[index];
    }
    // Return true only if it is marked as a full word
    return curr.isEnd;
}

6. Operation 3: Prefix Search (startsWith)

startsWith checks if any word in the Trie begins with the given prefix.

Step-by-Step Logic

1. Start at curr = root.
2. Traverse each character ch of the prefix.
3. Compute index = ch - 'a'.
4. If curr.children[index] is null, return false.
5. Advance curr to curr.children[index].
6. If all characters in the prefix are traversed successfully, return true immediately (ignoring isEnd).

Comparison: search vs startsWith

Java Implementation

public boolean startsWith(String prefix) {
    TrieNode curr = root;
    for (char ch : prefix.toCharArray()) {
        int index = ch - 'a';
        if (curr.children[index] == null) {
            return false; // Prefix broken
        }
        curr = curr.children[index];
    }
    return true; // Full prefix path found
}

7. Advanced Operation 4: Autocomplete / Suggestions using DFS

A core production use-case of Tries is generating auto-complete suggestions given a user-entered prefix string.

Architecture Optimization

To streamline suggestion collection during traversal, store the target string directly inside the terminal node during insertion:

// Inside insert() method, at terminal node:
curr.isEnd = true;
curr.word = word; // Storing complete word avoids dynamic string builder overhead

Logic & Workflow

1. Navigate from root down the path of the given prefix.
2. If the path terminates prematurely (null), return an empty list (no suggestions).
3. Once positioned at the end node of the prefix string, execute a Depth-First Search (DFS) from that node down all subtrees.
4. During DFS, whenever a node with isEnd == true is encountered, append its node.word to the result list.

Vertical Traversal Diagram for Prefix "ca"

Complete Java Implementation (Trie with Autocomplete)

import java.util.*;

public class Trie {
    
    // Internal node structure
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
        String word = "";
    }

    private final TrieNode root;

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

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (curr.children[index] == null) {
                curr.children[index] = new TrieNode();
            }
            curr = curr.children[index];
        }
        curr.isEnd = true;
        curr.word = word; // Store full word at terminal node
    }

    // Search full word
    public boolean search(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        return curr.isEnd;
    }

    // Search prefix
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        return true;
    }

    // Get suggestions for a prefix
    public List<String> getSuggestions(String prefix) {
        TrieNode curr = root;
        List<String> result = new ArrayList<>();

        // Step 1: Navigate to the end node of the prefix
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (curr.children[index] == null) {
                return result; // Return empty list if prefix does not exist
            }
            curr = curr.children[index];
        }

        // Step 2: Perform DFS from the prefix endpoint
        dfs(curr, result);
        return result;
    }

    // DFS Helper to explore all subtree branches
    private void dfs(TrieNode node, List<String> result) {
        if (node == null) return;

        // If terminal node reached, collect stored word
        if (node.isEnd) {
            result.add(node.word);
        }

        // Explore all 26 possible branches
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                dfs(node.children[i], result);
            }
        }
    }
}

8. Time and Space Complexity Analysis

Complexity Matrix

Detailed Complexity Breakdown

• Insertion Time Complexity — $O(L)$:
  • Iterates $L$ times (once per character). Each array access and node creation takes $O(1)$ time.
• Space Complexity — $O(N \times L)$:
  • Where $N$ is the total number of inserted words and $L$ is the average length of a word.
  • In the absolute worst-case scenario (where words share no common prefix), total nodes allocated will be $N \times L$.
  • In practice, space consumption is significantly lower due to shared common prefix nodes.
• Auto-Complete Suggestions Time — $O(L + M \times K)$:
  • Navigating to the prefix node takes $O(L)$.
  • DFS traversal visits $M$ matching word nodes, taking $O(M \times K)$ time to collect all matches.

9. Real-World Practical Pitfalls & Edge Cases

1. Memory Overhead of Fixed Array Size (26 Pointers)

• Pitfall: Allocating new TrieNode[26] for every single character node creates many null references in memory, especially when the tree is sparse.
• Solution: For large or dynamic alphabets (e.g., Unicode, case-sensitive ASCII), replace the array representation with a hash map:
  JAVA

  Copy

  class DynamicTrieNode {
      Map<Character, DynamicTrieNode> children = new HashMap<>();
      boolean isEnd = false;
  }
  

2. Case Sensitivity & Character Range Limitations

• Pitfall: Standard ch - 'a' indexing throws ArrayIndexOutOfBoundsException if non-lowercase characters (e.g., spaces, capital letters, digits) are inserted.
• Solution: Normalize inputs via word.toLowerCase() before processing, or dynamically adjust array boundaries.

3. Infinite Recursion / Null Pointer in DFS

• Pitfall: Calling DFS without verifying whether sub-branches are null causes explicit NullPointerException runtime crashes.
• Solution: Always check node.children[i] != null before recursively invoking DFS.

10. Summary and Key Takeaways

1. Prefix Optimization: A Trie (Prefix Tree) is structured specifically to enable $O(L)$ time prefix matching, outperforming linear array searches ($O(N \times L)$) and hash map limitations.
2. Character Paths: Nodes do not explicitly need to store their own character; their character identity is determined by their array index position in the parent's children array (index = ch - 'a').
3. Terminal Marker (isEnd): Differentiates between valid complete words and intermediate path prefixes.
4. Shared Prefixes: Words with identical prefixes (e.g., "cat", "car", "cart") reuse the exact same prefix nodes ("ca"), providing high storage efficiency for related text datasets.
5. Search vs StartsWith: search(word) demands both a complete path and isEnd == true, whereas startsWith(prefix) only demands path existence.
6. Autocomplete via DFS: Suggestions are generated by navigating to the terminal prefix node and executing a Depth-First Search to collect all downstream terminal words.
7. Terminal Word Caching: Storing the full word string directly inside terminal nodes eliminates string concatenation overhead during DFS traversal.
8. Array vs Map Tradeoff: A fixed 26-element array provides optimal $O(1)$ lookup speed for fixed lower-case English keys, whereas a HashMap<Character, TrieNode> provides flexible memory footprint for generalized character sets.