Implement TRIE (Prefix Tree) — Insert, Search, and StartsWith

The Trie (pronounced "try", derived from the word retrieval) is an advanced tree-like data structure used to store and retrieve strings dynamically with optimal time complexity. Unlike hash tables or balanced binary search trees, a Trie enables lightning-fast prefix-based searching, making it indispensable for features like autocomplete, spell checkers, IP routing, and dictionary searches.

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

Imagine building a text editor or search engine that needs to support three core operations on a dynamic set of words:

1. Insert (insert(word)): Add a new word into the repository.
2. Search (search(word)): Check if an exact word exists in the repository.
3. Prefix Match (startsWith(prefix)): Check if any previously inserted word begins with a given prefix.

Status Quo & Bottlenecks

• Using Hash Sets / Hash Maps: Inserting and exact searching take $O(L)$ time (where $L$ is the length of the word). However, checking for prefixes (startsWith) requires scanning every single stored word to check if it starts with the prefix, leading to $O(N \times L)$ time complexity (where $N$ is the total number of words), which is unacceptably slow for massive dictionaries.
• Using Sorting / Binary Search (Arrays/Lists): Storing words in a sorted list allows binary search for exact matches, but prefix searches still require linear scans or complex lower-bound range queries.

The Solution: A Trie solves this by sharing common prefixes among words, reducing search and insertion times to strictly $O(L)$, independent of the total number of words $N$ stored in the structure.

2. Core Mental Model & The Reference Node Analogy

Real-Life Analogy: The Postal Sorting Office / Dictionary Tree

Think of a Trie as a massive, multi-level hallway of postal lockers or alphabet waystations:

• You always begin your journey at the Root (an empty station representing nothing).
• To spell the word "apple", you step to the a locker. From a, you open a door leading to a sub-hallway containing p. From that p, you go to another p, then l, then e.
• If multiple words share the same beginning (e.g., "apple" and "apps"), they share the exact same path for "app" and only diverge when their characters differ (l vs s).

3. Anatomy of a Trie Node

A Trie is constructed using nodes (implemented as struct in C++ or class in Java). Each node contains two essential components:

1. An Array of Links (Pointers): An array of size 26 (Node* links[26]) representing the lowercase English alphabet from 'a' to 'z'. Indexing is achieved via character - 'a' (e.g., 'a' maps to index 0, 'b' to 1, ..., 'z' to 25).
2. A Boolean Flag (boolean flag): A marker initialized to false. When a word terminates at this specific node, the flag is flipped to true, indicating that a complete valid word ends here.

4. Step-by-Step Evolution: The Insert Operation

Let us trace how words are inserted into an empty Trie. Suppose we insert: ["apple", "apps", "apxl", "bac", "bat"].

Step-by-Step Execution for "apple":

1. Start at the Root.
2. Examine the first character 'a' (Index 0). Does root.links[0] exist?
   • No: Create a new Trie node, assign it to root.links[0], and set its flag to false.
3. Move our pointer to the newly created node for 'a'.
4. Examine character 'p'. Does its link exist? If not, create a new node and move forward.
5. Repeat for the second 'p', 'l', and 'e'.
6. At the final character 'e', set the node's flag = true to signify that a complete word ends here.

5. Search Operation: Exact Word Lookup

When searching for an exact word (e.g., "apps" vs "appl"):

1. Start at the Root.
2. Iterate through each character of the target word.
3. Check if the corresponding link exists in the current node's links array:
   • If a link is null, the word does not exist in the Trie. Return false.
   • If the link exists, traverse to that child node and proceed to the next character.
4. After traversing all characters of the word, check the final node's boolean flag:
   • If flag == true, the word exists. Return true.
   • If flag == false, the characters form a prefix of another word, but the exact word was never inserted. Return false.

6. StartsWith Operation: Prefix Validation

The startsWith(prefix) operation is identical to the search operation except for the final step:

• You traverse through the prefix characters starting from the Root.
• If any character link encounters a null, return false.
• If you successfully traverse all characters of the prefix without hitting a null, immediately return true—regardless of whether the final node's flag is true or false. This confirms that at least one word in the Trie starts with this prefix.

7. Comparative Synthesis: Trie vs. Hash Set vs. Sorted List

Note: $L$ is the length of the word, $N$ is the total number of words stored, and $\Sigma$ is the alphabet size (26 for lowercase English letters).

8. Industry-Standard C++ Implementation

Below is the clean, modular, production-grade implementation of the Trie data structure in C++. Notice how helper methods (containsKey, put, get, setEnd, isEnd) are encapsulated to keep the code readable, maintainable, and interview-ready.

#include <iostream>
#include <string>
using namespace std;

// Step 1: Define the structure of an individual Trie Node
struct Node {
    Node* links[26];
    bool flag = false;

    // Checks if the reference key (character) exists
    bool containsKey(char ch) {
        return (links[ch - 'a'] != nullptr);
    }

    // Creates a new reference node at the given character index
    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    // Retrieves the reference node for a given character
    Node* get(char ch) {
        return links[ch - 'a'];
    }

    // Marks the current node as the end of a valid word
    void setEnd() {
        flag = true;
    }

    // Returns whether a valid word ends at this node
    bool isEnd() {
        return flag;
    }
};

class Trie {
private:
    Node* root;

public:
    // Initialize your data structure here
    Trie() {
        root = new Node();
    }

    // Inserts a word into the trie
    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
                node->put(word[i], new Node());
            }
            // Move to the reference node
            node = node->get(word[i]);
        }
        node->setEnd();
    }

    // Returns if the word is in the trie
    bool search(string word) {
        Node* node = root;
        for (int i = 0; i < word.length(); i++) {
            if (!node->containsKey(word[i])) {
                return false;
            }
            node = node->get(word[i]);
        }
        return node->isEnd();
    }

    // Returns if there is any word in the trie that starts with the given prefix
    bool startsWith(string prefix) {
        Node* node = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!node->containsKey(prefix.ch - 'a' /* syntactic representation */ )) { // Standard index check below:
            }
            // Clean implementation:
            if (!node->containsKey(prefix[i])) {
                return false;
            }
            node = node->get(prefix[i]);
        }
        return true;
    }
};

9. Summary and Key Takeaways

• Definition: A Trie is a specialized tree data structure used for efficient retrieval of keys in a dataset of strings, heavily optimized for prefix operations.
• Node Architecture: Each Trie node contains an array of 26 pointers (links) for lowercase English letters and a boolean flag (isEnd) to mark word boundaries.
• Time Efficiency: All primary operations (insert, search, startsWith) execute in $O(L)$ time, where $L$ is the length of the target string, completely independent of the total dictionary size $N$.
• Space-Time Tradeoff: Tries consume more memory than traditional arrays or hash maps due to allocating 26 pointer slots per node, but they offer unmatched prefix lookup performance.
• Modular Coding Best Practices: Splitting functionality into atomic helper methods (containsKey, put, get, setEnd) separates concerns, ensures clean readability, and impresses interviewers with production-grade engineering habits.