Tries: Prefix Trees for Efficient String Operations

A trie (pronounced “try”) is a tree structure optimized for string operations. Unlike hash tables that store keys with no inherent connection, tries exploit common prefixes to share storage across keys. This makes prefix-based operations—starts with, autocomplete, longest common prefix—efficient.

The key insight: each node represents a prefix, and edges represent characters. The word “apple” creates the path a → p → p → l → e. The word “app” follows a→p→p, sharing nodes with “apple”. This prefix sharing is why tries excel when keys share common prefixes.

Introduction

A trie (prefix tree) is a tree structure optimized for string operations, exploiting common prefixes to share storage across keys. Where a hash table stores keys with no inherent relationship, tries organize keys by their prefix structure—the path from root to a node represents a prefix, and nodes mark where words end. This enables efficient prefix-based operations that would require scanning all keys in a hash table.

Tries excel at autocomplete, IP routing (longest prefix match), spell checking, and any scenario where you need to find all keys starting with a given prefix. The core operation complexity is O(m) where m is the key length—not dependent on the number of stored keys. Memory cost is higher than hash tables when keys share no common prefixes, but well-structured string data typically shares significant prefix structure.

In this guide, you’ll implement a trie with insert, search, and starts_with operations, build autocomplete functionality with DFS-based enumeration, and explore advanced operations like longest common prefix and prefix counting. We’ll look at compression strategies (radix trees) that reduce memory by merging single-child nodes, and compare tries against hash tables and suffix arrays for different use cases.

Trie Structure

graph TD
    ROOT["root"] --> A["a"]
    A --> AP["ap"]
    AP --> APP["app"]
    APP --> APPLE["apple"]
    APP --> B["ban"]

    ROOT2["root"] --> C["b"]
    C --> CA["ba"]
    CA --> CAN["ban"]

For words “apple” and “ban”: the root connects to ‘a’ and ‘b’. ‘a’ leads through ‘p’ → ‘p’ → ‘l’ → ‘e’ (apple), while ‘b’ → ‘a’ → ‘n’ (ban). Each node holds a children dict mapping characters to child nodes, and is_end marks word endings.

Trie Implementation

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False  # Marks end of a word
        self.count = 0  # Number of words passing through this node


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

    def insert(self, word):
        """O(m) where m is word length."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1  # Track prefix frequency
        node.is_end = True

    def search(self, word):
        """O(m) exact match search."""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        """O(m) check if any word starts with prefix."""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix):
        """Helper: find node at end of prefix path."""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def delete(self, word):
        """O(m) delete word."""
        def _delete(node, word, depth):
            if depth == len(word):
                if not node.is_end:
                    return False  # Word doesn't exist
                node.is_end = False
                return len(node.children) == 0  # Can delete if no children

            char = word[depth]
            if char not in node.children:
                return False  # Word doesn't exist

            should_delete_child = _delete(node.children[char], word, depth + 1)

            if should_delete_child:
                del node.children[char]
                return len(node.children) == 0 and not node.is_end

            return False

        if self.search(word):
            _delete(self.root, word, 0)

Common Trie Operations

def autocomplete(trie, prefix, max_results=10):
    """Return up to max_results words starting with prefix."""
    node = trie._find_node(prefix)
    if not node:
        return []

    results = []

    def dfs(node, path):
        if len(results) >= max_results:
            return

        if node.is_end:
            results.append(''.join(path))

        for char, child in node.children.items():
            path.append(char)
            dfs(child, path)
            path.pop()

    dfs(node, list(prefix))
    return results


def longest_common_prefix(trie):
    """Find longest common prefix among all words in trie."""
    result = []
    node = trie.root

    # Continue while node has exactly one child and is not end of a word
    while len(node.children) == 1 and not node.is_end:
        char, node = next(iter(node.children.items()))
        result.append(char)

    return ''.join(result)


def word_search(trie, board, rows, cols):
    """
    Find all words on board that exist in trie.
    Board cells connected horizontally/vertically.
    Similar to Boggle game.
    """
    found = []

    def dfs(r, c, node, path):
        if node.is_end:
            found.append(''.join(path))
            node.is_end = False  # Avoid duplicates

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return

        char = board[r][c]
        if char not in node.children:
            return

        node = node.children[char]
        path.append(char)

        # Try all four directions
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dfs(r + dr, c + dc, node, path)

        path.pop()

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in trie.root.children:
                dfs(r, c, trie.root, [])

    return found

Prefix Count and Ranking

def prefix_count(trie, prefix):
    """Count how many words start with prefix."""
    node = trie._find_node(prefix)
    return node.count if node else 0


def kth_smallest_prefix(trie, k):
    """
    Find kth smallest string in lexicographic order.
    Uses DFS in alphabetical order.
    """
    result = []

    def dfs(node, path):
        if not node:
            return

        if node.is_end:
            result.append(''.join(path))
            if len(result) >= k:
                return

        for char in sorted(node.children.keys()):
            dfs(node.children[char], path + [char])
            if len(result) >= k:
                return

    dfs(trie.root, [])
    return result[-1] if len(result) == k else None


class TrieMap:
    """Trie with key-value storage."""

    def put(self, key, value):
        node = self.root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.value = value
        node.is_end = True

    def get(self, key):
        node = self._find_node(key)
        return node.value if node and node.is_end else None

    def shortest_prefix_of(self, query):
        """Find shortest prefix of query that's a key in trie."""
        node = self.root
        prefix = []
        for char in query:
            if char not in node.children:
                break
            node = node.children[char]
            prefix.append(char)
            if node.is_end:
                return ''.join(prefix)
        return None

    def longest_prefix_of(self, query):
        """Find longest prefix of query that's a key in trie."""
        node = self.root
        prefix = []
        last_end = None
        for char in query:
            if char not in node.children:
                break
            node = node.children[char]
            prefix.append(char)
            if node.is_end:
                last_end = ''.join(prefix)
        return last_end

When to Use Tries

Use tries when:

• You need prefix-based operations (autocomplete, search suggestions)
• You’re doing IP routing (longest prefix match)
• You need efficient prefix counting or ranking
• Keys share common prefixes (which strings often do)

Don’t use tries when:

• Keys have no common prefixes (hash table is more space-efficient)
• You only need exact match lookup (hash table is simpler)
• Memory is extremely constrained

Trie vs Hash Table

Operation	Trie	Hash Table
Insert	O(m)	O(1) avg
Search	O(m)	O(1) avg
Prefix search	O(m + k)	O(n)
Sorted iteration	O(n log m)	O(n log n)
Space	O(ALPHABET × m × n)*	O(n)

*m = key length, n = number of keys **Trie space depends on prefix sharing

Production Failure Scenarios and Mitigations

Tries in production systems fail in predictable ways. Understanding these failure modes helps you design resilient implementations.

Memory Exhaustion from Unbounded Growth

Scenario: A autocomplete service inserts user search queries into a trie. Attackers or runaway scripts continuously insert unique queries, causing memory to grow until the service crashes.

Detection: Monitor trie node count and total memory usage. Set alerts at 70% and 85% of allocated memory thresholds.

Mitigation:

• Implement trie size limits with eviction policies (LRU for least-recently-used prefixes)
• Cap the maximum depth of inserted strings
• Periodically prune nodes with count=1 that represent single-use prefixes
• Use a separate process or container with hard memory limits

Cascade Failure from Shared Trie Infrastructure

Scenario: Multiple features share a single trie instance for different purposes (autocomplete, spell-check, routing). One feature receives a traffic spike, causing memory pressure that degrades all features.

Detection: Track per-feature resource consumption separately. Monitor allocation rate vs GC pressure.

Mitigation:

• Isolate feature-specific tries into separate processes or memory namespaces
• Implement per-tenant tries in multi-tenant systems
• Add circuit breakers that reject requests from noisy features

Latency Spikes from Large Result Sets

Scenario: A prefix search returns thousands of results because the prefix is too short (e.g., “a” matches 50,000 words). The DFS traversal blocks the thread, causing latency spikes for all users.

Detection: Monitor prefix search result counts and p99 latency per prefix length.

Mitigation:

• Enforce maximum result set sizes with early termination
• Limit minimum prefix length for autocomplete (typically 2-3 characters)
• Implement pagination for result traversal
• Add timeout guards around DFS operations

Data Corruption from Concurrent Modification

Scenario: Multiple threads simultaneously insert and delete words in a non-thread-safe trie implementation. Node references become inconsistent, causing crashes or silent data loss.

Detection: Run stress tests with concurrent read/write operations. Use thread sanitizers in testing.

Mitigation:

• Use thread-safe trie implementations with proper locking
• Consider read-write locks when read operations dominate
• Implement lock-free tries for high-concurrency workloads
• Add integrity verification passes during maintenance windows

Trade-Off Table: Trie Variants

Different trie implementations offer different trade-offs. Choose based on your workload characteristics.

Variant	Space Efficiency	Search Speed	Insert Speed	Best Use Case
Standard Trie	O(ALPHABET × m × n)	O(m)	O(m)	General-purpose when memory is available
Compressed Trie (Patricia/Radix)	O(n) to O(total chars)	O(m)	O(m)	Sparse keys with long common prefixes
Ternary Search Tree	O(n)	O(m log A)	O(m log A)	Memory-constrained environments, variable alphabets
Double-Array Trie	O(n)	O(m)	O(m)	Production systems needing fast and compact tries
DAWG (Directed Acyclic Word Graph)	Near-optimal	O(m)	O(m)	Large dictionary storage with maximum sharing
Suffix Tree	O(n)	O(m)	O(n)	Complex pattern matching, biological sequences

Key selection criteria:

• Memory-constrained? Use Ternary Search Tree or Double-Array Trie
• Keys share long prefixes? Compressed Trie reduces space dramatically
• Need maximum sharing? DAWG offers near-optimal suffix sharing
• Fixed alphabet, high throughput? Double-Array Trie provides best balance

Observability Checklist

Monitor these metrics to keep trie-based services healthy.

Core Metrics

• Trie node count (total nodes, depth distribution)
• Memory usage (RSS, heap allocations)
• Insert/search/startWith operation latency (p50, p95, p99)
• Operation throughput (operations/second)
• Cache hit rate for frequently-accessed prefixes

Health Signals

• Node count growth rate (should stabilize after initial bulk load)
• Memory fragmentation ratio
• Lock contention percentage (for threaded implementations)
• Failed allocation count
• Eviction rate from bounded tries

Alerting Thresholds

• Memory usage > 70% of limit: warning
• Memory usage > 85% of limit: critical, trigger scale-out or eviction
• p99 latency > 100ms for any operation: investigate
• Node count approaching configured maximum: prepare capacity action

Distributed Tracing

• Trace prefix search operations end-to-end
• Include prefix length and result count in span attributes
• Correlate trie operations with upstream request traces

Security Notes

Tries store sensitive data and have specific security considerations.

Information Disclosure

Risk: Tries can leak information about stored data through access patterns, timing differences, or memory content examination.

Mitigation:

• Use constant-time comparison for search operations to prevent timing attacks
• Consider encrypting trie contents at rest
• Implement request rate limiting to prevent probing attacks that infer stored prefixes

Input Validation

Risk: Maliciously long strings or unusual character sets can cause resource exhaustion.

Mitigation:

• Enforce maximum key length limits (typically 256-1024 characters)
• Validate character set matches expected alphabet
• Sanitize or reject keys containing control characters
• Set memory limits per-request to prevent single-request exhaustion

Multi-Tenant Isolation

Risk: In multi-tenant systems, one tenant’s data could leak to another through trie structure or prefix observation.

Mitigation:

• Use per-tenant trie instances with strict process isolation
• Never expose trie structure or node-level metadata in logs
• Implement proper authentication and authorization at the trie access layer
• Consider privacy-preserving techniques like differential privacy for aggregate prefix statistics

Compressed Trie (Radix Tree) Deep Dive

A compressed trie (also called a radix tree or Patricia trie) reduces memory by merging single-child nodes into edges labeled with substrings. This optimization is critical in production systems where standard trie memory overhead becomes prohibitive.

Compression Mechanism

In a standard trie, inserting “apple” creates nodes along the path: a → p → p → l → e. A compressed trie merges non-branching segments into a single edge labeled “apple”. If “app” is later inserted, the edge splits at the common prefix boundary:

• If the existing edge is “apple” and we insert “app”, the edge splits into “app” as a prefix edge and “le” as a child edge. The node at “app” becomes a branching point and is marked as end-of-word.
• If we insert “apt” into a trie containing “apple”, the edge “apple” splits at “ap”, creating two branches: “ple” (existing) and “t” (new).

Edge Splitting Algorithm

When inserting a word into a compressed trie, for each edge label at the current node:

1. If the remaining suffix of the word starts with the entire edge label, follow the edge and continue traversal.
2. If the remaining suffix shares a partial common prefix with the edge label, split the edge:
   • Create a new internal node at the common prefix boundary
   • The new node gets two children: the old child (with the remaining suffix of the edge label) and a new child (with the remaining suffix of the insertion word)
3. If no edge matches, create a new edge for the remaining suffix.

When to Choose Compressed Trie

Aspect	Standard Trie	Compressed Trie
Node count	O(total characters)	O(number of keys)
Memory	High (many single-child nodes)	Low (merged nodes)
Insert complexity	Simple	Complex (edge splitting and merging)
Search speed	O(m)	O(m)
Best for	Dense keysets, frequent inserts	Sparse keysets, read-heavy workloads

Real-World Usage

• Linux kernel: IPv4/IPv6 routing tables use radix trees (lib/radix-tree.c)
• Redis: RAFT (Redis Auto-Compressed Trie) indexes sorted set members
• Nginx: URL routing and location matching uses prefix-based lookup
• CDN systems: Content routing with longest prefix matching on URL paths

Quick Recap Checklist

• Trie stores strings by sharing common prefixes
• Each node has children dict and is_end flag
• Search, insert, starts_with all O(m) where m is key length
• Excellent for prefix operations, autocomplete, IP routing
• Can store additional data (counts, values) at nodes
• Space intensive if keys have no common prefixes

Interview Questions

5. How would you implement a spell checker using a trie?

Insert a dictionary of valid words into a trie. To check a word's spelling, traverse the trie character by character. If the path doesn't exist or the final node isn't marked as end-of-word, the word is misspelled. For suggestions, use edit-distance techniques:

• DFS from the prefix node to collect words within a small Levenshtein distance
• Generate candidate corrections by inserting, deleting, or substituting characters and checking each against the trie
• Rank suggestions by edit distance and word frequency (store frequency at each end node)

6. What are the trade-offs between a trie and a ternary search tree (TST)?

Both support prefix-based operations but differ in space and speed:

• Trie: O(m) search, O(ALPHABET × nodes) space — fast but memory-heavy for sparse keysets
• TST: O(m log A) search, O(nodes) space — uses three pointers per node (left, middle, right) instead of a full alphabet array
• TSTs are preferred in memory-constrained environments or when the alphabet is large (Unicode)
• Tries are faster for dense, small-alphabet datasets (e.g., English words with 26 letters)
• TSTs can be balanced for better worst-case performance

7. How do you handle deletion in a trie? Walk through the algorithm and edge cases.

Deletion in a trie must handle three cases:

• Word doesn't exist: Return without modification
• Word exists as a leaf (no children): Remove all nodes along its path that have no other branches (recursive cleanup)
• Word exists but has children: Only unset the is_end flag; keep the nodes because they are shared with other words

The standard approach uses recursive descent: delete the last character, then on the way back up, delete nodes that have is_end = false and no remaining children. Always decrement the count field if maintaining prefix frequency counts.

8. How would you use a trie to solve the "word break" problem (segment a string into dictionary words)?

Problem: Given a string and a dictionary, determine if the string can be segmented into space-separated dictionary words.

• Insert all dictionary words into a trie for O(m) prefix lookup
• Use dynamic programming: dp[i] = true if substring s[0:i] can be segmented
• For each position i where dp[i] is true, traverse the trie starting from s[i] and mark dp[j] = true for every word end reached
• The trie speeds up prefix matching from O(n²) to O(n × m) worst-case, where m is max word length
• For collecting all segmentations, use backtracking with trie-guided prefix search

9. How can you make a trie thread-safe for concurrent access?

Several strategies depending on concurrency requirements:

• Coarse-grained locking: Use a single read-write lock on the entire trie. Simple but limits throughput under write-heavy workloads
• Fine-grained locking: Lock individual nodes during traversal. Enables higher concurrency but adds complexity and deadlock risk
• Optimistic concurrency: Use copy-on-write — readers proceed lock-free while writers create new node versions. Good for read-dominated workloads
• Lock-free tries: Use atomic compare-and-swap (CAS) operations on node children. Requires careful memory ordering and handles the ABA problem
• Per-node locks with hand-over-hand locking: Acquire the current node's lock, then the next, then release the previous. Prevents deadlocks by consistent lock ordering

10. How would you find all words in a trie that match a pattern with wildcards ('?' for single char, '*' for any sequence)?

Use recursive DFS with pattern matching at each node:

• '?' wildcard: At the current position in the pattern, try all children of the current node recursively
• '*' wildcard: Try two possibilities — consume the '*' by matching zero characters (advance pattern, stay at same node) or match one character (advance in both trie and pattern)
• Use memoization to avoid recomputation: key by (node, pattern_index)
• Early termination: if pattern is exhausted, collect all words in the subtree rooted at the current node
• Time complexity: O(alphabet_size^wildcards) worst-case, but bounded by the number of nodes in practice

11. How would you serialize and deserialize a trie for persistence?

Two common approaches:

• Pre-order traversal with structure markers: Traverse the trie recursively. For each node, emit its children count, then recurse. Use a sentinel or bit flag to mark is_end. Deserialize by reading the node structure and reconstructing children
• Flat array representation: Store nodes in a contiguous array where each node contains an index into the array for each child (null = -1). This is how double-array tries work and enables memory-mapped persistence
• Include node metadata (counts, values) in the serialization format
• Consider versioning the serialization format for forward compatibility

12. How would you count distinct substrings of a string using a suffix trie?

Insert all suffixes of the string into a trie. The number of distinct substrings equals the number of nodes in the trie (excluding the root).

• For string "abc", suffixes are "abc", "bc", "c". Inserting all three builds a trie where each path from root to any node represents a distinct substring
• Nodes = a, b, c, ab, bc, abc — 6 distinct substrings (correct: a, b, c, ab, bc, abc)
• Time complexity: O(n²) to insert all suffixes, but can be reduced to O(n) using a suffix tree (Ukkonen's algorithm)
• Space optimization: Use a compressed suffix tree (suffix tree) instead of a naive suffix trie for O(n) nodes

13. How would you implement a trie for multi-tenant isolation in a SaaS autocomplete service?

Multi-tenant trie isolation requires preventing data leakage and resource contention between tenants:

• Per-tenant trie instances: Each tenant gets a separate trie stored in isolated memory regions or containers
• Tagged nodes: Use a single trie but tag each node with tenant IDs. Queries filter by tenant tag during traversal
• Resource quotas: Enforce per-tenant node count and memory limits. Implement per-tenant eviction policies (LRU)
• Rate limiting: Apply per-tenant rate limits on insert and search operations to prevent noisy-neighbor problems
• Observability: Track per-tenant metrics — node count, latency, eviction rate — for capacity planning and billing

14. How do you choose between a standard trie and a compressed trie (radix tree) for a production system?

Consider these factors:

• Prefix overlap: If keys share long common prefixes (URLs, file paths, IP addresses), compressed trie saves significant memory
• Insert/delete frequency: Standard trie is simpler and faster for write-heavy workloads; compressed trie's edge splitting adds overhead on inserts
• Memory budget: Compressed trie reduces node count from O(total characters) to O(number of keys) — critical in constrained environments
• Implementation complexity: Standard trie is straightforward to implement correctly; compressed trie requires careful edge-splitting logic and is prone to bugs
• Search speed: Both offer O(m) search; compressed trie may traverse fewer edges due to multi-character labels

15. What is a double-array trie and why is it attractive for production systems?

A double-array trie represents the trie using two parallel arrays — BASE and CHECK — where each node's state lives at a numerical array index instead of in a heap-allocated object with pointers. This eliminates pointer chasing and makes traversal cache-friendly.

Space: O(n) with no per-node dictionary overhead. Speed: O(m) per operation with deterministic array offsets — no hash function, no collisions. Drawback: Resizing is expensive, so double-array tries suit static or rarely-modified dictionaries best. Dynamic updates usually require a full rebuild.

NLP toolkits like MeCab and Julius use them, along with high-throughput routing systems and dictionary-based compressors.

16. How does Aho-Corasick relate to tries, and when would you choose one over the other?

Aho-Corasick is a trie with failure links added. A standard trie finds words that start at a given position; Aho-Corasick finds every pattern from a set anywhere in the text in a single left-to-right scan. The failure links let you pick up the next match without resetting to the root.

If your input is a key and you need prefix operations (autocomplete, routing), use a trie. If your input is text and you need to match many patterns simultaneously (log parsing, spell checking, keyword detection), use Aho-Corasick. Time complexity for Aho-Corasick: O(text length + number of matches).

17. What is the relationship between a trie and a suffix automaton, and when would you choose each?

A trie encodes prefixes of multiple strings. A suffix automaton (SAM) encodes all substrings of a single string in near-minimal form, sharing suffixes via endpos equivalence classes.

If you're storing a fixed set of keys and doing prefix lookups, a trie is the straightforward choice. If you're analyzing one long string (DNA sequences, log corpora, text search) and need substring queries or longest common substring between two strings, a SAM gives O(n) construction and compact representation for that workload. SAMs can't easily handle multiple independent key sets the way tries do.

18. How would you implement a case-insensitive trie, and what are the trade-offs?

The simpler approach: lowercase everything before inserting and querying. The trie stays standard, but you lose the original case — "Apple" and "apple" are indistinguishable.

If you need case-preserving results with case-insensitive matching, store the original case separately. Map each lowercase character to a list of child nodes representing different casings. This doubles or triples your child pointer overhead, but keeps the original string available for display.

In practice: most autocomplete systems just lowercase everything and call it a day. Only add case-preserving logic if your product genuinely needs it — the complexity rarely pays for itself otherwise.

19. How would you implement prefix-based frequency ranking to find the top-K most common prefixes?

Each node in the trie already tracks a count incremented on every insert pass-through. Once the trie is built, walk all nodes once, pushing each node's count and prefix into a min-heap capped at size K. When the heap overflows, drop the smallest. Result: O(n log K) total.

For streaming data where counts update live, apply exponential time-decay to counts — multiply by a decay factor on each update so recent prefixes bubble up. You skip the heap entirely on writes and only rebuild the ranking occasionally, during low-traffic windows.

If you need range queries over prefix frequencies (e.g., "all prefixes between count 1000 and 5000"), a Fenwick tree over a sorted node array handles that more naturally than a heap.

20. How does a trie compare to a deterministic finite automaton (DFA) for regex-style pattern matching?

A trie is a restricted DFA with no cycles — each state is a prefix, and all paths terminate. A full DFA for a regex can have loops (Kleene star, +) and handles operators like alternation and quantification. Tries are to finite sets of literal strings what DFAs are to regular languages.

Matching a known word list? A trie beats a regex engine — fewer moving parts, better space efficiency. Matching patterns with wildcards and operators? You need a DFA or NFA (usually built via Thompson's construction). Regex engines internally use trie-like structures for the literal components of patterns, but the operator machinery is where DFA/NFA complexity lives.

Further Reading

• GeeksforGeeks - Trie Data Structure — Comprehensive tutorial with implementation examples in multiple languages
• Wikipedia - Trie — Detailed overview of trie variants, history, and asymptotic analysis
• Radix Tree (Patricia Trie) — Wikipedia — Deep dive into the compressed trie variant used in Linux kernel routing
• The Power of Tries — Coding Horror — Practical autocomplete implementation with real-world insights
• Ternary Search Trees — Dr. Dobb’s — In-depth article on memory-efficient trie alternatives
• USACO Guide - Trie — Competitive programming applications and practice problems with solutions

Conclusion

Tries use more memory than hash tables but give you O(m) operations for insert, search, and prefix checks where m is key length—no matter how many keys you’re storing. They shine for autocomplete, routing tables, and any workload built around prefix matching. If you only need exact-match lookups and space is a concern, a hash table is the simpler option. For another data structure that handles connectivity problems, see Union-Find: Disjoint Set Data Structure.