Trie-Based String Search: Algorithm Analysis and Code

Introduction and Core Concepts

Trie-based string search is a specialized tree data structure technique designed to solve one of computing's most frequent problems: efficiently storing and retrieving strings by their prefixes. The term "trie" comes from the word "retrieval," pronounced as "try," and was first described by Edward Fredkin in 1960. Unlike general-purpose data structures such as hash tables or binary search trees that treat keys as atomic units, a trie decomposes strings into individual characters and shares common prefixes among multiple keys, creating a highly optimized pathway for string operations.

At its core, a trie is a rooted tree where each edge represents a character and each node represents a prefix of some string in the dataset. The root node is associated with the empty string, and every path from the root to a node spells out a prefix. Nodes that correspond to complete words or keys are explicitly marked, typically with a boolean flag such as is_end_of_word. This prefix-sharing property is what makes trie-based string search exceptionally powerful for tasks where prefix matching is central, such as autocomplete, spell checking, and IP routing.

Why does trie-based string search matter in modern systems? In an era where applications handle millions of strings — from search engine queries and dictionary words to URLs and genomic sequences — the ability to answer questions like "does this word exist?" or "what words start with 'pre'?" in time proportional to the length of the query string, rather than the size of the dataset, is transformative. Hash tables can answer exact matches quickly but cannot efficiently enumerate all keys with a given prefix without scanning the entire table. Binary search on a sorted array requires O(log n) comparisons, each of which may cost O(L) character comparisons. A trie achieves O(L) time for all core operations where L is the length of the string, independent of n, the number of strings stored. This makes it indispensable for latency-sensitive applications like web search suggestions and network packet forwarding.

Key Terminology

Understanding trie-based string search requires familiarity with a few core concepts. A node contains an array or hash map of child pointers (one per possible character), a flag indicating terminal nodes, and optionally a count or payload. An edge is labeled with a single character from the alphabet. The alphabet size, often denoted as Σ or m, directly impacts memory consumption; for lowercase English letters it is 26, for extended ASCII it is 256, and for Unicode it can be much larger. The depth of a node equals the length of the prefix it represents.

Another important distinction is between a standard trie, a compressed trie (also called a radix tree or Patricia trie), and a ternary search trie. While the classic trie has one node per character, compressed variants merge chains of nodes with a single child to save space, making them preferred for large-scale storage systems and in-memory databases. The choice of variant depends on the tradeoff between memory efficiency and implementation simplicity.

How It Works

A trie organizes strings by incrementally building a tree of characters. Insertion starts at the root and processes the input string character by character. For each character, the algorithm checks whether a child node for that character already exists. If it does, it follows that edge; if not, it creates a new node and creates the edge. After processing the final character, it marks the current node as terminal. This means that inserting "apple" and "app" will share the nodes for 'a' -> 'p' -> 'p', with the node for the second 'p' marked as terminal for "app" and a further branch for 'l' -> 'e' leading to the terminal node for "apple".

Searching for a string follows the same traversal path. To determine if a word exists, the trie walks from the root following the characters of the query. If at any point the required child does not exist, the search fails and the word is absent. If the traversal completes, the algorithm checks the terminal flag of the final node; only if it is true is the word considered present. This distinction is crucial: the path for "app" exists when "apple" is stored, but "app" should only be reported as found if it was explicitly inserted. The same traversal principle underpins prefix search: to check if any word starts with a given prefix, the algorithm only needs to verify that the path for the prefix exists, regardless of the terminal flag.

Deletion and enumeration build on this foundation. Deleting a word requires unmarking its terminal flag and then pruning nodes that are no longer needed. If the deleted word is a prefix of another word (e.g., deleting "app" when "apple" exists), only the flag is cleared and no nodes are removed. If the word has no other words sharing its suffix branch, the leaf nodes can be deleted bottom-up until a node is reached that is either terminal for another word or has more than one child. Prefix enumeration, used for autocomplete, first locates the node corresponding to the prefix and then performs a depth-first search (DFS) from that node to collect all terminal descendants, effectively listing every word in the subtree.

Structural Properties

The shape of a trie is deterministic given a set of strings and is independent of insertion order, unlike a binary search tree where order affects balance. The total number of nodes is bounded by the total number of characters across all strings, but in practice is much smaller due to prefix sharing. For example, storing 100,000 English words with an average length of 8 characters might require only 300,000 nodes instead of 800,000 if stored separately. Each node stores references to children, which can be implemented as a fixed-size array for small alphabets (fast O(1) access) or as a hash map/dictionary for large or sparse alphabets (memory efficient).

Another key property is that the height of the trie is bounded by the length of the longest string, not the number of strings. This guarantees predictable performance even as the dataset scales to millions of entries. However, this also means that for very long strings, such as URLs or DNA sequences, the trie can become deep and pointer chasing may impact cache performance, which motivates compressed variants.

Implementation

Implementing a trie in Python is straightforward because dictionaries provide a flexible way to store children for any alphabet without preallocating large arrays. Below are four complete, production-ready implementations covering core operations, prefix search, deletion, and advanced features like wildcard search and word counting.

Basic Trie Structure and Insertion

class TrieNode:
    def __init__(self):
        # Dictionary to store child nodes: char -> TrieNode
        self.children = {}
        # True if node represents end of a valid word
        self.is_end_of_word = False
        # Optional: count how many words pass through this node
        self.prefix_count = 0

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

    def insert(self, word: str) -> None:
        """Insert a word into the trie. Time: O(L) where L = len(word)"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.prefix_count += 1
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        """Return True if word exists exactly in trie."""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        """Return True if any word starts with prefix."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Autocomplete and Prefix Enumeration

class TrieWithAutocomplete(Trie):
    def _collect_words(self, node, prefix, results):
        """DFS helper to collect all words under node."""
        if node.is_end_of_word:
            results.append(prefix)
        for char, child_node in node.children.items():
            self._collect_words(child_node, prefix + char, results)

    def autocomplete(self, prefix: str) -> list:
        """Return all words with given prefix. Time: O(P + N) where P is prefix length, N is number of matched words."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        results = []
        self._collect_words(node, prefix, results)
        return results

    def count_words_with_prefix(self, prefix: str) -> int:
        """Count words sharing prefix using prefix_count optimization."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.prefix_count

    def count_total_words(self) -> int:
        """Count total words via DFS."""
        def dfs(n):
            count = 1 if n.is_end_of_word else 0
            for child in n.children.values():
                count += dfs(child)
            return count
        return dfs(self.root)

Deletion with Pruning

class TrieWithDeletion(Trie):
    def delete(self, word: str) -> bool:
        """Delete word from trie. Returns True if deleted, False if not found."""
        def _delete(node, word, depth):
            if depth == len(word):
                # Reached end of word
                if not node.is_end_of_word:
                    return False  # Word not present
                node.is_end_of_word = False
                # If leaf node, signal to delete this node
                return len(node.children) == 0
            char = word[depth]
            if char not in node.children:
                return False
            should_delete_child = _delete(node.children[char], word, depth + 1)
            if should_delete_child:
                del node.children[char]
                # Delete current node if it is not end of another word and has no other children
                return not node.is_end_of_word and len(node.children) == 0
            return False

        # Use wrapper to handle prefix_count decrement
        if not self.search(word):
            return False
        # Decrement prefix counts along path
        node = self.root
        for char in word:
            node = node.children[char]
            node.prefix_count -= 1
        _delete(self.root, word, 0)
        return True

Advanced: Wildcard Search and Longest Common Prefix

class AdvancedTrie(Trie):
    def search_with_wildcard(self, pattern: str) -> bool:
        """Support '.' as wildcard matching any single character."""
        def dfs(node, index):
            if index == len(pattern):
                return node.is_end_of_word
            char = pattern[index]
            if char == '.':
                # Try all children
                for child in node.children.values():
                    if dfs(child, index + 1):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return dfs(node.children[char], index + 1)
        return dfs(self.root, 0)

    def longest_common_prefix(self) -> str:
        """Find longest common prefix among all words in trie."""
        prefix = []
        node = self.root
        # Traverse while node has exactly one child and is not terminal
        while len(node.children) == 1 and not node.is_end_of_word:
            char = next(iter(node.children))
            prefix.append(char)
            node = node.children[char]
        return "".join(prefix)

    def get_all_words(self) -> list:
        """Return all words stored in trie in lexicographic order."""
        result = []
        def dfs(node, path):
            if node.is_end_of_word:
                result.append("".join(path))
            for char in sorted(node.children.keys()):
                path.append(char)
                dfs(node.children[char], path)
                path.pop()
        dfs(self.root, [])
        return result

Step-by-Step Example

To make trie-based string search concrete, let us walk through building a trie with the words: ["apple", "app", "apricot", "bat", "batch", "batman"] and then querying it. This example highlights prefix sharing, terminal flags, and how autocomplete works.

Step 1: Insert "apple". Starting from the root, we create nodes for 'a' -> 'p' -> 'p' -> 'l' -> 'e'. Each new node is initialized with an empty children map and is_end_of_word = False. After processing 'e', we set its flag to True. The trie now has 5 edges and 5 non-root nodes.

Step 2: Insert "app". We traverse 'a' -> 'p' -> 'p' using existing nodes. Upon reaching the second 'p', we simply mark that node as terminal (it was previously non-terminal). No new nodes are created. This demonstrates prefix sharing: "app" reuses the prefix of "apple" and only updates metadata. The trie now contains two words but still has only 5 non-root nodes.

Step 3: Insert "apricot". We follow 'a' -> 'p' (existing), but the next character 'r' does not exist as a child of the second 'p'. We create a new branch: 'r' -> 'i' -> 'c' -> 'o' -> 't', marking 't' as terminal. The trie now branches at the second 'p' node, which has two children: 'l' and 'r'.

Step 4: Insert "bat", "batch", "batman". From the root, 'b' is a new child. We create 'b' -> 'a' -> 't' and mark 't' as terminal for "bat". For "batch", we reuse 'b'-'a'-'t' and add 'c' -> 'h'. For "batman", we again reuse 'b'-'a'-'t' and add 'm' -> 'a' -> 'n'. The node for 't' now has two children ('c' and 'm') and is itself terminal.

Query Walkthrough: Searching for "app" traverses 'a','p','p' and finds is_end_of_word == True, so it returns True. Searching for "appl" traverses to 'l' but finds is_end_of_word == False, so it returns False — the prefix exists but is not a stored word. Searching for "batmobile" fails at 'm' after "bat" because 'm' child exists (for batman) but the next character 'o' does not match 'a', so it returns False. A prefix query starts_with("ap") succeeds after traversing 'a','p'. An autocomplete query autocomplete("bat") locates the node for 't' and DFS collects ["bat", "batch", "batman"].

Visual Representation

Conceptually, the final trie looks like this (terminal nodes marked with *):

# root
# ├── a ── p ── p* ── l ── e*   (apple, app)
# │              └── r ── i ── c ── o ── t*  (apricot)
# └── b ── a ── t* ── c ── h*  (bat, batch)
#                   └── m ── a ── n*  (batman)

# Example traversal trace for search("apricot"):
# root -> a (found) -> p (found) -> p (found) -> r (found) -> i (found) -> c (found) -> o (found) -> t (found, is_end=True) => True

This example also illustrates deletion. Deleting "app" would simply clear the terminal flag on the second 'p' node, leaving the structure intact for "apple" and "apricot". Deleting "apricot" would prune the branch 'r'-'i'-'c'-'o'-'t' entirely, since no other word shares that suffix. Deleting "bat" would only clear the flag on 't', preserving 'c'-'h' and 'm'-'a'-'n' for the other words.

Complexity Analysis

The performance of trie-based string search is characterized by its dependence on string length rather than dataset size, which is its defining advantage. For a word of length L, an alphabet size of Σ, and a total of n words with total characters N, the analysis is as follows.

Time complexity for insertion, exact search, and prefix search is O(L) in all cases. Each operation processes each character once, performing a hash map lookup or array access per character. This is effectively O(1) per character, so the total is linear in the string length. Unlike hash tables where collisions can degrade performance, or balanced BSTs where comparisons depend on n, trie operations are deterministic and independent of n. The worst case is the same as the best case — there is no input-dependent variation except for early exit when a prefix is missing, which can make unsuccessful searches slightly faster.

Space complexity is O(N * Σ) in the naive array-based implementation, or O(N) in the dictionary-based implementation where N is the total number of characters. In the worst case where no prefixes are shared (e.g., all words start with different characters), the trie stores N nodes. In the best case with maximum sharing (e.g., words like "a", "aa", "aaa"), the number of nodes is close to the length of the longest word. Each node stores child pointers; with an array of size Σ, memory is Σ per node, while with a hash map it is proportional to the actual number of children, which is typically small.

Autocomplete and enumeration have additional cost. Finding the prefix node is O(P) where P is prefix length, but collecting all K words under that prefix requires traversing the entire subtree, which is O(K * L_avg) where L_avg is average word length in the subtree, or more precisely O(number of nodes in subtree). This is optimal because any algorithm must output those K words.

A critical nuance is that O(L) can be slower than O(1) hash table lookup for very long strings if L is large, but for typical natural language words (L < 20) the constant factors are small. Memory overhead is the primary tradeoff: a trie can use significantly more memory than a hash table due to node objects and pointers, especially for sparse datasets. For example, storing 1 million random 10-character strings with little prefix overlap will create nearly 10 million nodes, each with dictionary overhead, which can exceed several hundred megabytes.

Variations and Optimizations

While the classic trie is elegant, several variations optimize it for specific constraints such as memory, alphabet size, and cache performance. The choice of variation can dramatically affect real-world efficiency.

The Compressed Trie (Radix Tree / Patricia Trie) merges chains of nodes that have only one child into a single edge labeled with a substring. For instance, the chain 'a'-'p'-'p' where intermediate nodes have only one child could be compressed into an edge labeled "app". This reduces the number of nodes from O(N) to O(n) where n is the number of words, and significantly improves cache locality. Patricia tries (Practical Algorithm To Retrieve Information Coded In Alphanumeric) go further by compressing at the bit level and are widely used in IP routing tables where binary strings are stored.

The Ternary Search Trie (TST) combines the space efficiency of BSTs with the time efficiency of tries. Each node stores a single character and has three children: left (characters less than node char), middle (next character in word), and right (characters greater than node char). This reduces memory from Σ pointers per node to just 3, at the cost of O(L log Σ) search time in the worst case. TSTs are ideal when the alphabet is large (e.g., Unicode) and memory is constrained, and they naturally support near-neighbor search.

Other important optimizations include Array vs. Hash Map for Children. For small, dense alphabets like 'a'-'z' or '0'-'9', a fixed array of size 26 or 10 provides O(1) access with minimal overhead and excellent cache performance. For large or sparse alphabets, a hash map or sorted list is more memory efficient. Some implementations use a hybrid: an array for the first few levels and hash maps deeper in the tree. Double-Array Tries use two parallel arrays (base and check) to represent the trie in a compact, cache-friendly form, enabling very fast search with minimal memory, commonly used in morphological analysis and spell checkers for languages like Japanese.

Additional Techniques

Counting and Frequency Tries augment each node with a count of how many words pass through or end at that node, enabling O(P) prefix counting and frequency-based autocomplete ranking. Persistent Tries create a new version of the trie for each insertion without modifying previous versions by path copying, useful for versioned dictionaries and functional programming. Suffix Tries and Suffix Trees store all suffixes of a text, enabling O(M) substring search for a pattern of length M, which is fundamental in bioinformatics and full-text search. Finally, Concurrent Tries use lock-free techniques or fine-grained locking to support high-throughput parallel inserts and searches in multi-threaded servers.

Real-World Applications

Trie-based string search is not an academic curiosity; it powers critical infrastructure across the web, databases, networks, and devices. Its ability to perform prefix search in time proportional to the prefix length makes it uniquely suited for interactive and high-throughput systems.

In web search and autocomplete, tries are the backbone of type-ahead suggestions. When a user types "tri" into a search engine, the system queries a trie containing billions of past queries to return completions like "trie algorithm", "trip advisor", and "trivago" in milliseconds. The trie is often stored in memory across distributed servers, with frequency counts at nodes to rank suggestions by popularity. Similarly, IDEs and code editors use tries for variable and function name autocompletion, providing instant feedback as developers type.

In networking and IP routing, routers must perform longest prefix match to forward packets. An IP address like 192.168.1.0/24 is a binary string prefix, and the routing table stores thousands of such prefixes. A binary trie (or Patricia trie) allows the router to find the most specific matching prefix for a destination address in O(32) or O(128) steps for IPv4/IPv6, which is essential for line-rate forwarding at 100 Gbps. Without tries, routing would require linear scanning or hashing with complex fallback logic.

In databases and storage engines, tries are used for indexing string keys, especially for range and prefix queries. Systems like Apache Lucene and LevelDB use trie-like structures (FSTs - Finite State Transducers) to store term dictionaries, enabling fast prefix and wildcard searches over inverted indexes. Spell checkers and dictionaries use tries to efficiently find words within edit distance 1 or 2 of a misspelled word by DFS with pruning, which is far faster than checking every word in the dictionary.

Beyond these, tries are used in bioinformatics for storing and searching DNA sequences where the alphabet is {A,C,G,T}, in data compression (e.g., dictionary-based compression), and in natural language processing for tokenization and n-gram storage. Even phone keyboards that predict the next word use a trie of language model n-grams to efficiently retrieve candidates.

Comparison with Alternatives

Choosing the right data structure for string search requires understanding the tradeoffs between time, space, and supported operations. While tries excel at prefix operations, other structures may be superior for pure exact-match workloads or memory-constrained environments.

Hash tables offer average O(L) time for exact search (hashing the string costs O(L)) and O(1) expected lookup after hashing, which is often faster than a trie for exact matches due to lower constant factors. However, they cannot support prefix search, ordered traversal, or autocomplete without scanning all n keys, which costs O(n*L). They also have no ordering guarantees and can suffer from hash collisions and resizing overhead. Hash tables are best when only exact membership is needed and memory is a concern.

Balanced binary search trees (AVL, Red-Black) and sorted arrays with binary search store strings in lexicographic order, enabling O(log n) search with O(L) string comparisons per comparison, leading to O(L log n) time. They support ordered iteration and prefix range queries via binary search bounds, but finding all words with a prefix still requires scanning the range, which can be O(K + log n). They are more memory efficient than tries (storing strings contiguously) but slower for prefix-heavy workloads.

Ternary Search Tries (TSTs) provide a middle ground: they use less memory than tries (3 pointers per node vs. Σ) and support prefix search, but have O(L log Σ) worst-case time and are more complex to implement. Sorted arrays are extremely cache-friendly and memory efficient but have O(n*L) insertion cost, making them suitable for static datasets.

In practice, many systems combine structures. For example, a web server might use a hash table for exact URL routing and a trie for prefix-based route matching (e.g., "/api/v1/*"). Databases often use a trie-like FST for the term dictionary but hash tables for document storage. The decision should be driven by the query pattern: if more than 10-20% of queries are prefix-based, a trie typically wins despite higher memory.

Common Mistakes and Best Practices

Implementing trie-based string search correctly requires attention to edge cases and performance pitfalls that can lead to bugs, memory leaks, or degraded performance.

A frequent mistake is forgetting the terminal flag distinction. Beginners often return True as soon as the path exists, without checking is_end_of_word. This causes search("app") to incorrectly return True when only "apple" was inserted. Always verify the flag after traversal. Similarly, during deletion, failing to handle the case where the deleted word is a prefix of another word leads to accidental removal of shared nodes. The deletion algorithm must only prune nodes that are not terminal and have no children.

Another pitfall is inefficient child storage. Using a fixed array of size 26 for lowercase English is fine, but using size 256 or larger for Unicode without consideration wastes enormous memory (256 pointers * 8 bytes * millions of nodes). Conversely, using a Python dict for a dense alphabet like 'a'-'z' adds hash overhead where an array would be faster. Profile your alphabet distribution: if the trie is dense and alphabet is small, use arrays or lists; if sparse or alphabet is large, use dicts. In Python, children = {} is the pragmatic default.

Recursion depth and stack overflow is a subtle issue. Recursive DFS for autocomplete or deletion can exceed Python's recursion limit (default 1000) for very long strings or deep tries (e.g., genomic sequences). Prefer iterative implementations using an explicit stack for production code, or increase recursion limit carefully. Also, not handling empty strings correctly — the root node itself may need to be marked terminal if empty string is a valid key — causes off-by-one errors.

Best Practices

To build robust trie systems, follow these guidelines: First, normalize input before insertion and search — convert to consistent case, Unicode normalization (NFC), and strip whitespace to avoid duplicate entries like "Apple" vs "apple". Second, augment nodes with metadata such as prefix_count, word_count, or frequency scores to support O(P) prefix counting and ranking without DFS. This is essential for autocomplete relevance. Third, consider iterative deletion and use garbage collection wisely — in languages with manual memory management, ensure pruned nodes are freed; in Python, deleting dict entries is sufficient. Fourth, compress when appropriate — if memory is a concern and the dataset is static, build a double-array trie or radix tree after bulk insertion. Fifth, benchmark with realistic data — trie performance is highly data-dependent; test with your actual string distribution, not just random strings. Finally, handle concurrency — if the trie is shared across threads, use read-write locks: multiple readers can traverse concurrently, but writers need exclusive access during insertion/deletion to avoid seeing partially constructed nodes.

Testing should cover edge cases: empty trie, empty string, duplicate inserts, deletion of non-existent words, prefix that is also a word, and very long strings. Use property-based testing to verify that search(word) is True iff word was inserted and not deleted.

Interview Questions

Trie-based string search is a favorite in technical interviews because it tests understanding of trees, recursion, string manipulation, and tradeoff analysis. Below are common questions with solution strategies.

1. Implement a Trie with Insert, Search, and StartsWith

This is the classic LeetCode 208 question. The interviewer expects you to design TrieNode with children and is_end, and implement three methods in O(L) time. Key points to mention: time is independent of n, space is O(N), and you handle the terminal flag correctly. Be prepared to discuss array vs. dict for children and to code iteratively to avoid recursion limits. Follow up: "How would you support deletion?" — describe the pruning logic.

2. Design an Autocomplete System

Given a list of sentences and frequencies, design a system that returns the top 3 suggestions for a prefix as the user types. Solution: Build a trie where each node stores a list of top 3 hot sentences in its subtree (updated during insertion). For query input(c), traverse to the prefix node and return its hot list in O(P) time. Discuss how to handle real-time updates and tie-breaking by lexicographic order. Complexity: O(N*L) build, O(P) query. Optimization: Use a min-heap at each node to maintain top K efficiently.

3. Word Search II - Find All Words on a Board

Given a 2D board of characters and a list of words, find all words that can be formed by adjacent cells (horizontal/vertical) without reusing a cell. Brute force DFS for each word is O(n * 4^L). Optimized solution: Insert all words into a trie, then DFS from each board cell, traversing the trie simultaneously and pruning when the prefix does not exist. This reduces search space dramatically because many paths are pruned early. Mention backtracking with visited set and early termination when node has no children. This demonstrates the trie's power for multi-pattern search.

4. Replace Words with Shortest Root (Prefix Replacement)

Given a dictionary of roots (e.g., ["cat", "bat", "rat"]) and a sentence, replace each word in the sentence with its shortest root that is a prefix, or leave it unchanged if no root is a prefix. Example: roots ["cat","cattle"], sentence "cattle was rattled by battery" -> "cat was rat by bat". Solution: Insert roots into trie, then for each word in sentence, traverse the trie character by character; the first terminal node encountered is the shortest root. This is O(S) where S is total characters in sentence, far faster than checking each root per word. Discuss handling multiple roots sharing prefixes.

5. Longest Common Prefix and Maximum XOR

Two related problems: (a) Find the longest common prefix among an array of strings — insert all strings into a trie and traverse while the current node has one child and is not terminal. (b) Given an array of integers, find the maximum XOR of any two numbers — build a binary trie of 32-bit representations, then for each number, greedily traverse the trie choosing the opposite bit when possible to maximize XOR. This shows the trie's versatility beyond strings to binary data. For (b), time is O(n * 32) and space is O(n * 32), which is optimal for the problem.

When answering interview questions, always state complexity, discuss tradeoffs (trie vs. hash table vs. sorting), handle edge cases (empty input, duplicates), and write clean, commented code with proper escaping of comparisons. Interviewers value clarity on why a trie is chosen — specifically for prefix operations — over just coding it.