Skip to content
Data Structures & Algorithms

Trie Data Structure interview questions and answers

28 questions, 28 with code. About 1 h 57 min to read them all.

By TestLab · Updated

Plan for an interview
28 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a trie, and how does it work?

A trie (prefix tree) is a tree for storing strings in which each edge represents one character and each path from the root spells a prefix. Words that share a prefix share the same path, and a node is marked with an is_end flag when a complete word ends there. Insert, search and prefix checks all take O(L) time for a string of length L, independent of how many words are stored, which makes tries ideal for prefix queries such as autocomplete.

Read full answer

Applies toautocomplete and search suggestions, spell checkers, IP routing (longest prefix match), word games, dictionary and prefix-counting problems

Structure

Words: car, cat, cart, dog

(root)
 ├── c
 │   └── a
 │       ├── r*      (car)
 │       │   └── t*  (cart)
 │       └── t*      (cat)
 └── d
     └── o
         └── g*      (dog)

* marks is_end = True. The prefix ca is stored once and shared by three words.

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # True if a word ends here

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _find(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

t = Trie()
for w in ["car", "cat", "cart", "dog"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.starts_with("ca"), t.search("cow"))
# True False True False

search("ca") is False because ca is only a prefix, not a stored word; starts_with("ca") is True.

Complexity

Operation Time Notes
Insert O(L) Creates at most L new nodes
Search O(L) Follows L edges
Prefix check (starts_with) O(P) P = prefix length
List words with a prefix O(P + size of the output subtree)
Space O(total characters) nodes; up to O(total characters x alphabet) with fixed-size child arrays

Using a dict of children stores only the edges that exist, which saves a lot of space compared with a fixed array of 26 (or 256) slots per node when nodes have few children.

Why Use a Trie

  • Prefix queries are natural: all words with a prefix sit in one subtree.

  • Lexicographic order: a depth-first traversal visiting children in sorted order yields words in sorted order.

  • Shared prefixes reduce repeated work (for example checking many words against a grid in Word Search II).

  • Predictable time: O(L) regardless of dictionary size, with no hash collisions.

Limitations

  • Memory overhead: one node per character, each with its own children map; often more memory than a hash set of strings.

  • Poor cache locality with pointer-based nodes.

  • For exact-match lookups only, a hash table is usually simpler and faster.

Variants (Briefly)

  • Compressed trie / radix tree: merges chains of single-child nodes into one edge labelled with a string.

  • Suffix trie / suffix tree: stores all suffixes of a text for fast substring search.

  • Ternary search tree: each node has less, equal and greater children; less memory than wide tries.

  • Bitwise (binary) trie: stores numbers bit by bit; used for maximum XOR and IP routing.

Interview Tip

Define a trie as a prefix tree with one character per edge and an is_end flag, write insert, search and starts_with, and give O(L) complexity. Mentioning the dict-of-children space saving and the radix-tree variant shows depth.

2

What advantages do tries have over hash tables?

Tries beat hash tables mainly for prefix-based and ordered operations. A trie can find all keys with a given prefix, check whether any key starts with a prefix, find the longest stored prefix of a query (as in IP routing), and list keys in sorted order, all efficiently. A hash table can answer only exact-match queries quickly; prefix searches require scanning every key. Tries also give predictable O(L) lookups with no collisions or rehashing, and they share storage for common prefixes. Hash tables usually win for plain exact lookups and memory efficiency.

Read full answer

Applies tochoosing a data structure for dictionaries, autocomplete, routing tables, spell checkers and string-keyed indexes

Comparison

Capability Trie Hash table
Exact lookup O(L) O(L) to hash the key, then O(1) average (O(n) worst case with heavy collisions)
Prefix search (“all keys starting with pre”) O(P + results) O(n x L): scan every key
“Any key starts with prefix?” O(P) O(n x L)
Longest prefix match O(L) walk Try every prefix length: O(L^2) work with hashing each prefix
Sorted iteration Natural (DFS in child order) Requires sorting: O(n log n)
Worst-case guarantees O(L), no collisions Depends on the hash function; vulnerable to collision attacks without randomised hashing
Resizing Grows node by node Periodic rehashing of all keys
Shared prefixes Stored once Each key stored in full
Memory Often higher (node and pointer overhead) Usually lower
Cache behaviour Pointer chasing, weaker Better, especially open addressing

Example: Prefix Search

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # True if a word ends here

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _find(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

    def with_prefix(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            n, path = stack.pop()
            if n.is_end:
                out.append(path)
            for ch in sorted(n.children, reverse=True):
                stack.append((n.children[ch], path + ch))
        return out

words = ["apple", "app", "apply", "apt", "banana"]
t = Trie()
for w in words:
    t.insert(w)
print(t.with_prefix("app"))                         # ['app', 'apple', 'apply']
print(sorted(w for w in words if w.startswith("app")))   # same result, but scans every key
# ['app', 'apple', 'apply']

The trie visits only the app subtree; the hash set must examine every word.

When the Advantages Matter

  • Autocomplete: return suggestions for each typed character quickly.

  • IP routing: longest-prefix match on binary tries.

  • Spell checking: explore neighbouring paths for corrections.

  • Word games and Word Search II: prune the search as soon as a path is not a prefix of any word.

  • Prefix counting: store a count in each node to answer “how many words start with X” in O(P).

When a Hash Table Is Better

  • Only exact-match lookups are needed.

  • Memory is tight, or keys share few prefixes.

  • Keys are not strings or sequences.

Interview Tip

Lead with prefix search, longest prefix match and sorted iteration as the trie’s key advantages, mention predictable O(L) lookups without collisions, then acknowledge that hash tables are usually better for exact lookups and memory. That balanced answer is what interviewers expect.

3

What are the advantages and disadvantages of a trie?

A trie’s main advantages are fast prefix operations (O(P) prefix checks and efficient “all words with this prefix” queries), O(L) insert and search independent of the number of words, shared storage for common prefixes, natural lexicographic ordering, and no hash collisions. Its main disadvantages are high memory use (a node per character with child pointers or maps), poor cache locality, more complex implementation (especially deletion and compression), and slower exact lookups than a hash table for many workloads.

Read full answer

Applies tochoosing structures for autocomplete, dictionaries, spell checkers, routing tables and string-matching problems

Advantages

Advantage Explanation
Prefix queries starts_with in O(P); list all completions by exploring one subtree
Predictable time Insert and search are O(L), regardless of dictionary size
Longest prefix match Walk the query and remember the last word end (IP routing, URL routing)
Sorted order DFS in child order produces keys in lexicographic order
Shared prefixes Common prefixes stored once (useful for words like inter, international, internet)
No collisions or rehashing Deterministic behaviour; no worst-case hashing attacks
Pruned searches Stop exploring as soon as a path is not a prefix (Word Search II, Boggle)
Prefix counts Store counters per node for “how many words start with X”

Disadvantages

Disadvantage Explanation Mitigation
Memory overhead Each node holds a map or array of children plus flags Dict children instead of 26-slot arrays; radix trees; DAWGs; double-array tries
Poor locality Following pointers causes cache misses Array-based or succinct tries; memory pools
Slower exact lookup than hashing in practice More pointer hops per character Use a hash table if only exact lookups are needed
Implementation complexity Deletion with pruning, compression, Unicode handling Use well-tested libraries (marisa-trie, pygtrie, datrie)
Wide alphabets Unicode makes fixed arrays impossible Hash-map children, byte-level tries on UTF-8
Little benefit with few shared prefixes Random keys (UUIDs) share little Prefer a hash table

Space Example

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def count_nodes(words):
    root, count = TrieNode(), 1
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
                count += 1
            node = node.children[ch]
        node.is_end = True
    return count

shared = ["inter", "internal", "internet", "interval", "interview"]
print(sum(map(len, shared)), count_nodes(shared))   # 38 17

Shared prefixes cut 38 characters down to 16 nodes plus the root, but each node is a Python object with a dict, so the real memory is still far larger than storing 38 characters in a hash set.

When to Use a Trie

  • Many prefix queries, such as autocomplete and search suggestions.

  • Longest-prefix matching, as in routing tables.

  • Word-game and grid search with pruning.

  • Ordered traversal of string keys.

When to Avoid It

  • Only exact-match lookups are needed.

  • Memory is very limited and keys share few prefixes.

  • A sorted array with binary search, or a database index, already meets the need.

Interview Tip

List the advantages (prefix operations, O(L) time, sorted order, no collisions) and disadvantages (memory, locality, complexity), and give a short rule for when to choose a trie over a hash table. Mentioning radix trees and dict-based children as ways to reduce memory shows practical knowledge.

4

How do you handle case sensitivity in a trie?

The usual way to handle case is to normalise keys before inserting and searching, for example with str.casefold() (better than lower() for full Unicode), so Apple, APPLE and apple share one path. If you must keep the original spelling, store it at the end node (for example a set of original forms or the most popular one) while searching on the normalised path. If case must be distinguished, keep a case-sensitive trie and, when needed, run case-insensitive searches by exploring both cases at each character, which costs more. Choose based on whether the application treats case as meaningful.

Read full answer

Applies toautocomplete, spell checkers, search indexes, command and identifier lookup, and internationalised text

Option 1: Normalise Everything (Most Common)

class TrieNode:
    def __init__(self):
        self.children, self.is_end, self.originals = {}, False, set()

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

    @staticmethod
    def _key(word):
        return word.casefold()

    def insert(self, word):
        node = self.root
        for ch in self._key(word):
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True
        node.originals.add(word)             # keep the original spelling(s)

    def search(self, word):
        node = self.root
        for ch in self._key(word):
            node = node.children.get(ch)
            if node is None:
                return set()
        return node.originals if node.is_end else set()

t = CaseInsensitiveTrie()
for w in ["Apple", "iPhone", "apple", "Straße"]:
    t.insert(w)
print(sorted(t.search("APPLE")))    # ['Apple', 'apple']
print(sorted(t.search("iphone")))   # ['iPhone']
print(sorted(t.search("STRASSE")))  # ['Straße']

casefold() maps German ß to ss, so STRASSE matches Straße, while lower() would leave ß unchanged and fail.

Option 2: Case-Sensitive Trie With Case-Insensitive Search

Keep exact keys, and explore both the lowercase and uppercase child at each step:

def search_ignore_case(node, word, i=0):
    if i == len(word):
        return node.is_end
    for ch in {word[i].lower(), word[i].upper()}:
        child = node.children.get(ch)
        if child and search_ignore_case(child, word, i + 1):
            return True
    return False

class Node:
    def __init__(self):
        self.children, self.is_end = {}, False

root = Node()
for w in ["GitHub", "gitlab"]:
    n = root
    for ch in w:
        n = n.children.setdefault(ch, Node())
    n.is_end = True
print(search_ignore_case(root, "github"), search_ignore_case(root, "GITLAB"))   # True True

This can branch at every letter (up to 2^L paths in the worst case), so it suits occasional queries, not hot paths.

Option 3: Two Tries or Dual Indexing

Maintain both a case-sensitive trie (for exact matching) and a normalised one (for suggestions). It uses more memory but keeps both query types fast.

Comparison

Approach Memory Case-insensitive query Exact-case query
Normalise at insert Lowest O(L) Check stored originals at the end node
Case-sensitive plus branching search Low Up to O(2^L) worst case O(L)
Two tries Highest O(L) O(L)

Practical Considerations

  • Unicode: use casefold(), and consider Unicode normalisation (NFC or NFKC via unicodedata.normalize) so composed and decomposed accents match. Some languages need locale-specific rules (Turkish dotted and dotless i).

  • Accents: for search, you may also strip diacritics (café to cafe) as an additional normalisation step.

  • Ranking: when suggesting completions, return the most common original form (for example iPhone rather than iphone).

  • Consistency: apply the same normalisation for inserts, searches and deletions.

Interview Tip

Recommend normalising with casefold() before insert and search, storing original forms at end nodes when display matters, and mention branching search or dual tries when case must be preserved. Pointing out Unicode cases like ß and Turkish i shows real-world awareness.

5

What are some practical applications of a trie?

Tries are used wherever prefixes matter: autocomplete and search suggestions, spell checking and correction, IP routing with longest-prefix matching, word games and puzzle solvers (Boggle, Scrabble, Word Search II), dictionary and prefix-count queries, URL and HTTP route matching, T9 and predictive text, string-matching algorithms (Aho-Corasick for many patterns), and bitwise tries for problems like maximum XOR. Compressed variants (radix trees) power in-memory indexes and routing tables in real systems.

Read full answer

Applies tosearch engines, mobile keyboards, networking, web frameworks, databases and coding interviews

Applications Overview

Application How the trie helps
Autocomplete Walk to the prefix node, then list or rank words in its subtree
Spell checking Fast dictionary lookup; explore nearby paths for edit-distance corrections
IP routing Binary or multibit tries find the longest matching prefix for a destination address
Word games Prune search paths that are not prefixes of any dictionary word
Multi-pattern search Aho-Corasick builds a trie of patterns plus failure links to find all matches in one pass
URL routing Radix trees match path segments (for example Go’s httprouter, and Echo)
Predictive text (T9) Map digit sequences to words through a trie
Prefix counting Counters at nodes answer “how many words start with X” in O(P)
Maximum XOR A binary trie of numbers picks the opposite bit at each level
Databases and key-value stores Radix trees and adaptive radix trees (ART) used as in-memory indexes (Redis uses a radix tree, rax, for streams)

Example: Prefix Counts

class Node:
    def __init__(self):
        self.children, self.count = {}, 0      # count = words passing through this node

def build(words):
    root = Node()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, Node())
            node.count += 1
    return root

def count_prefix(root, prefix):
    node = root
    for ch in prefix:
        node = node.children.get(ch)
        if node is None:
            return 0
    return node.count

root = build(["apple", "app", "apricot", "banana", "band"])
print(count_prefix(root, "ap"), count_prefix(root, "ban"), count_prefix(root, "c"))   # 3 2 0

Example: Maximum XOR of Two Numbers

def max_xor(nums, bits=31):
    root = {}
    for x in nums:
        node = root
        for b in range(bits, -1, -1):
            node = node.setdefault((x >> b) & 1, {})
    best = 0
    for x in nums:
        node, cur = root, 0
        for b in range(bits, -1, -1):
            bit = (x >> b) & 1
            if 1 - bit in node:            # prefer the opposite bit to maximise XOR
                cur |= 1 << b
                node = node[1 - bit]
            else:
                node = node[bit]
        best = max(best, cur)
    return best

print(max_xor([3, 10, 5, 25, 2, 8]))   # 28  (5 XOR 25)

Example: Longest Prefix Match (Routing)

Routes 10.0.0.0/8, 10.1.0.0/16 and 10.1.2.0/24 are stored as bit paths. For destination 10.1.2.7, walk the bits and remember the last node that holds a route: /24 wins as the most specific match. Production routers use compressed multibit tries or hardware (TCAM) for speed.

Interview Tip

Name several applications across search (autocomplete, spell check), networking (longest prefix match), games and algorithms (Aho-Corasick, maximum XOR), and briefly explain why a trie helps each one. A short code example such as prefix counting or maximum XOR makes the answer concrete.

6

How can a trie implement autocomplete functionality?

For autocomplete, insert every candidate phrase into a trie along with a score (popularity, recency or personal relevance). When the user types a prefix, walk to the prefix node in O(P), then collect the best completions from its subtree. To keep responses fast for short prefixes with huge subtrees, store the top-k suggestions at each node (precomputed when inserting), so a query is just walk the prefix, return the cached list. Add normalisation, typo tolerance and ranking, and cache results for very common prefixes.

Read full answer

Applies tosearch boxes, e-commerce product search, IDE code completion, command palettes, address and city pickers, and mobile keyboards

Basic Version: DFS From the Prefix Node

import heapq

class Node:
    def __init__(self):
        self.children = {}
        self.score = None              # set when a full phrase ends here

class Autocomplete:
    def __init__(self):
        self.root = Node()

    def insert(self, phrase, score):
        node = self.root
        for ch in phrase.casefold():
            node = node.children.setdefault(ch, Node())
        node.score = score

    def suggest(self, prefix, k=3):
        node = self.root
        for ch in prefix.casefold():
            node = node.children.get(ch)
            if node is None:
                return []
        results, stack = [], [(node, prefix.casefold())]
        while stack:
            n, text = stack.pop()
            if n.score is not None:
                results.append((n.score, text))
            for ch, child in n.children.items():
                stack.append((child, text + ch))
        return [t for _, t in heapq.nlargest(k, results)]

ac = Autocomplete()
for phrase, score in [("iphone 15", 90), ("iphone case", 70), ("ipad", 85),
                      ("iphone charger", 60), ("ipod", 20)]:
    ac.insert(phrase, score)
print(ac.suggest("ip"))       # ['iphone 15', 'ipad', 'iphone case']
print(ac.suggest("iphone c")) # ['iphone case', 'iphone charger']

This works, but for a prefix like a the subtree can contain millions of entries.

Optimised Version: Top-k Cached at Each Node

class Node:
    def __init__(self):
        self.children, self.top = {}, []     # top: list of (score, phrase), best first

class FastAutocomplete:
    def __init__(self, k=3):
        self.root, self.k = Node(), k

    def insert(self, phrase, score):
        node = self.root
        for ch in phrase.casefold():
            node = node.children.setdefault(ch, Node())
            node.top = sorted(node.top + [(score, phrase)], reverse=True)[: self.k]

    def suggest(self, prefix):
        node = self.root
        for ch in prefix.casefold():
            node = node.children.get(ch)
            if node is None:
                return []
        return [p for _, p in node.top]

fa = FastAutocomplete()
for phrase, score in [("iphone 15", 90), ("iphone case", 70), ("ipad", 85), ("ipod", 20)]:
    fa.insert(phrase, score)
print(fa.suggest("ip"), fa.suggest("ipo"))   # ['iphone 15', 'ipad', 'iphone case'] ['ipod']

Queries now take O(P + k). The cost moves to insertion (O(L x k)) and memory (k entries per node), which suits read-heavy systems. Score updates need care: re-insert or rebuild offline.

Production Design

Concern Approach
Ranking Popularity, click-through rate, recency, personalisation, business rules
Updates Rebuild the trie offline periodically (for example hourly) from query logs; hot-swap the new version
Scale Shard by prefix (first characters) or replicate the whole trie on each server; compress with radix trees
Latency Cache responses for popular prefixes at the edge or in the browser; debounce keystrokes on the client
Typos Fuzzy matching with bounded edit distance during traversal, or a separate spell-correction step
Normalisation Case folding, accent removal, whitespace trimming
Safety Filter offensive or blocked suggestions
Multi-word Index each word start too, so “case iphone” can match “iphone case”

Complexity

Version Query Insert Extra memory
DFS plus heap O(P + subtree size) O(L) None
Top-k per node O(P + k) O(L x k) O(nodes x k)

Interview Tip

Describe walking to the prefix node and collecting completions, then explain the top-k-per-node optimisation that makes queries O(P + k). Covering ranking, offline rebuilds, caching, typo tolerance and sharding shows you can take the design to production.

7

How is a trie used in IP routing to match IP prefixes?

Routers must find, for each destination address, the most specific route: the longest stored prefix that matches it (longest prefix match, LPM). A binary trie stores each route’s prefix as a path of bits (for example 10.1.0.0/16 uses the first 16 bits), with the route’s next hop stored at the node where the prefix ends. To look up an address, walk its bits from the root, remembering the last node that had a route; when the path ends, that remembered route is the answer. Lookup takes O(W) for an address of W bits (32 for IPv4, 128 for IPv6). Production systems use compressed and multibit tries (Patricia trees, LC-tries, Tree Bitmap) or hardware TCAM to cut memory accesses.

Read full answer

Applies torouters and Linux kernel routing (the FIB uses an LC-trie), firewalls and ACLs, CDN and cloud load balancers, IP geolocation databases

Example Routing Table

Prefix Next hop
0.0.0.0/0 (default) ISP
10.0.0.0/8 Core router A
10.1.0.0/16 Data centre B
10.1.2.0/24 Rack C

Destination 10.1.2.7 matches /0, /8, /16 and /24; the longest, /24, wins and the packet goes to Rack C. Destination 10.9.9.9 matches /0 and /8, so it goes to Core router A.

Implementation in Python (Binary Trie)

import ipaddress

class Node:
    __slots__ = ("children", "route")
    def __init__(self):
        self.children = [None, None]
        self.route = None

class RoutingTrie:
    def __init__(self):
        self.root = Node()

    def add(self, cidr, next_hop):
        net = ipaddress.ip_network(cidr)
        bits, node = int(net.network_address), self.root
        for i in range(net.prefixlen):
            b = (bits >> (31 - i)) & 1
            if node.children[b] is None:
                node.children[b] = Node()
            node = node.children[b]
        node.route = next_hop

    def lookup(self, ip):
        bits, node = int(ipaddress.ip_address(ip)), self.root
        best = node.route                       # default route, if any
        for i in range(32):
            node = node.children[(bits >> (31 - i)) & 1]
            if node is None:
                break
            if node.route is not None:
                best = node.route               # remember the longest match so far
        return best

rt = RoutingTrie()
rt.add("0.0.0.0/0", "ISP")
rt.add("10.0.0.0/8", "core-A")
rt.add("10.1.0.0/16", "dc-B")
rt.add("10.1.2.0/24", "rack-C")
for ip in ["10.1.2.7", "10.1.9.9", "10.9.9.9", "8.8.8.8"]:
    print(ip, "->", rt.lookup(ip))
# 10.1.2.7 -> rack-C
# 10.1.9.9 -> dc-B
# 10.9.9.9 -> core-A
# 8.8.8.8 -> ISP

Why a Trie Fits

  • Prefixes of different lengths nest naturally along one path.

  • LPM is a single walk, without testing each possible prefix length separately.

  • Inserting or withdrawing a route touches only its path, which matters when BGP updates arrive constantly.

Making It Fast in Practice

Technique Idea
Path compression (Patricia / radix trie) Skip chains of single-child nodes; store the bit index to test next
Multibit tries (stride k) Consume k bits per step (for example 8), cutting IPv4 lookups to about 4 memory accesses, at the cost of prefix expansion and memory
Level-compressed tries (LC-trie) Combine both; the Linux kernel’s IPv4 FIB uses an LC-trie
Tree Bitmap and similar encodings Compact multibit nodes, used in hardware and software routers
DIR-24-8 A large table indexed by the first 24 bits plus small second-level tables (used in DPDK)
TCAM hardware Compare an address with all prefixes in parallel and pick the longest match in one cycle

Complexity

  • Lookup: O(W) for a binary trie (W = 32 or 128); O(W / k) for stride k.

  • Insert and delete: O(W) plus any prefix expansion in multibit tries.

  • Memory: proportional to the number of prefixes times the path length, reduced by compression. A full Internet table has around a million IPv4 prefixes.

Interview Tip

Explain longest prefix match with a small routing table, show how a binary trie stores prefixes as bit paths and how lookup remembers the last route seen, and give O(W) complexity. Mentioning Patricia and multibit tries, the Linux LC-trie and TCAM shows you know how it is done at line rate.

8

How is a trie used in spell-checking and correction systems?

In a spell checker, a trie stores the dictionary: checking a word is an O(L) walk to see whether it ends at an is_end node. For corrections, the trie supports an efficient bounded edit-distance search: walk the trie while computing the Levenshtein distance row by row (one row per trie node, built from its parent’s row), and prune any branch whose best possible distance already exceeds the limit. Shared prefixes mean shared computation, so finding all words within distance 1 or 2 is far faster than comparing against every dictionary word. Candidates are then ranked by distance, word frequency and context.

Read full answer

Applies totext editors and word processors, search query correction ("did you mean"), mobile keyboards, OCR post-processing and code editors

Checking a Word

Walk the characters; if a child is missing, or the final node is not a word end, the word is misspelled. With case folding and Unicode normalisation applied first, this is O(L).

Finding Corrections: Levenshtein Search Over a Trie

class Node:
    def __init__(self):
        self.children, self.word = {}, None

def build(words):
    root = Node()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, Node())
        node.word = w
    return root

def suggestions(root, target, max_dist=1):
    results = []
    first_row = list(range(len(target) + 1))

    def walk(node, ch, prev_row):
        row = [prev_row[0] + 1]
        for i in range(1, len(target) + 1):
            insert_cost = row[i - 1] + 1
            delete_cost = prev_row[i] + 1
            replace_cost = prev_row[i - 1] + (target[i - 1] != ch)
            row.append(min(insert_cost, delete_cost, replace_cost))
        if node.word is not None and row[-1] <= max_dist:
            results.append((row[-1], node.word))
        if min(row) <= max_dist:                      # prune hopeless branches
            for next_ch, child in node.children.items():
                walk(child, next_ch, row)

    for ch, child in root.children.items():
        walk(child, ch, first_row)
    return sorted(results)

dictionary = ["hello", "help", "hell", "shell", "yellow", "jello", "world", "word"]
root = build(dictionary)
print(suggestions(root, "helo"))       # [(1, 'hell'), (1, 'hello'), (1, 'help')]
print(suggestions(root, "wrld"))       # [(1, 'world')]

Each trie node computes one row of the dynamic-programming table from its parent’s row, so the prefix hel is computed once for hell, hello and help.

Why the Trie Helps

Approach Work per misspelled word
Compare with every dictionary word O(N x L^2) for N words
Trie with row-by-row Levenshtein and pruning Visits only branches within the distance bound; shared prefixes computed once
Generate all edits and look up each (Norvig style) About 54L + 25 candidates at distance 1 for a 26-letter alphabet; grows quickly at distance 2

Ranking Corrections

  • Edit distance (smaller is better), possibly weighted by keyboard proximity (e next to r) or common typos.

  • Word frequency: prefer common words (store counts in end nodes).

  • Context: language models or n-grams choose between candidates (“their” vs “there”).

  • Personal dictionary: user-added words and frequently typed terms.

Other Trie Techniques in Spell Checking

  • Prefix pruning while typing: if no dictionary word starts with the typed prefix, flag it early.

  • Compact dictionaries: DAWGs (directed acyclic word graphs) or finite-state automata share both prefixes and suffixes; Hunspell-style checkers combine dictionaries with affix rules for morphology.

  • Alternatives: BK-trees for metric search; SymSpell (precomputed deletions) for very fast lookups at the cost of memory.

Complexity

  • Check: O(L).

  • Suggestions: depends on the dictionary and the distance bound; pruning keeps it far below scanning all words, especially for max distance 1 or 2.

Interview Tip

Explain dictionary lookup in O(L), then the row-by-row Levenshtein walk with pruning that reuses work across shared prefixes, and how candidates are ranked. Mentioning DAWGs, BK-trees or SymSpell as alternatives shows breadth.

9

What are the main strategies for implementing a trie?

The main trie implementation strategies differ in how each node stores its children: a fixed-size array indexed by character (fast, memory-hungry), a hash map or dict (flexible, space-efficient for sparse nodes), a sorted list or array of (char, child) pairs (compact, binary-searchable), a linked list of siblings (left-child right-sibling), or a ternary search tree (three children per node). Beyond node layout, there are structural variants: compressed tries / radix trees (merge single-child chains), double-array tries and succinct tries (compact array encodings), DAWGs (share suffixes too), and bitwise tries for integers and IP addresses.

Read full answer

Applies todictionaries, autocomplete, routing tables and string indexes, in Python, Java, C++, Go and Rust

Child-Storage Strategies

Strategy Child lookup Memory Best for
Fixed array (26 or 256 slots) O(1), very fast High: every node reserves every slot Small alphabets, dense tries, performance-critical code
Hash map / dict O(1) average Proportional to actual children General purpose, Unicode, sparse nodes
Sorted array of pairs O(log k) binary search Compact Read-heavy, static dictionaries
Linked list of siblings O(k) Compact Very sparse nodes, simple C implementations
Ternary search tree O(log alphabet) per character on average Low Memory-sensitive string sets with ordered operations

Fixed Array vs Dict in Python

class ArrayNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = [None] * 26          # 'a'..'z' only
        self.is_end = False

def insert_array(root, word):
    node = root
    for ch in word:
        i = ord(ch) - ord("a")
        if node.children[i] is None:
            node.children[i] = ArrayNode()
        node = node.children[i]
    node.is_end = True

class DictNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}                   # any character, only the ones used
        self.is_end = False

def insert_dict(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, DictNode())
    node.is_end = True

ra, rd = ArrayNode(), DictNode()
for w in ["tea", "ten", "to"]:
    insert_array(ra, w); insert_dict(rd, w)
print(sum(c is not None for c in ra.children), len(rd.children))   # 1 1

Both roots have one real child (t), but each array node always allocates 26 slots, while the dict holds only what exists.

Structural Variants

Variant Idea Benefit
Compressed trie / radix tree (Patricia) Edges labelled with strings; single-child chains merged Far fewer nodes; used in routers and in-memory indexes
Adaptive radix tree (ART) Node size adapts (4, 16, 48, 256 children) Fast and compact; used in database indexes (DuckDB, HyPer)
Double-array trie Two integer arrays (base, check) encode transitions Very compact, fast, cache-friendly; used in Japanese tokenisers such as MeCab
Succinct tries (LOUDS) Tree shape stored as bit vectors Near-minimal space for static dictionaries (marisa-trie)
DAWG / minimal automaton Shares common suffixes as well as prefixes Small spell-check and word-game dictionaries
Bitwise trie Binary digits as the alphabet Maximum XOR, IP routing, integer sets
Suffix trie / suffix tree Stores all suffixes of a text Substring search and string analytics
Ternary search tree less / equal / greater children Low memory with ordered traversal

Other Implementation Choices

  • What to store at nodes: is_end flag, counts (prefix counting), values (a map), top-k suggestions, or word references.

  • Memory management: node pools or arenas instead of individual allocations for speed and locality.

  • Iteration order: sorted children if lexicographic output is needed (arrays and sorted lists give this for free).

  • Mutability: static tries can be built once and encoded compactly; dynamic ones need cheap inserts and deletes.

  • Concurrency: copy-on-write or lock-free variants for many readers.

Choosing

  • Interview or general use: dict-based nodes with an is_end flag.

  • Lowercase-only, performance-critical code: 26-slot arrays.

  • Large static dictionaries: double-array, succinct trie or DAWG.

  • Long keys with shared prefixes, such as URLs or IPs: radix tree.

Interview Tip

Compare array, dict, sorted-list and sibling-list children with their time and space trade-offs, then mention structural variants: radix trees, double-array and succinct tries, DAWGs and ternary search trees. Recommending a choice for a specific scenario shows practical judgement.

10

How do you write code to insert a word into a trie?

To insert a word, start at the root and process the word one character at a time: if the current node already has a child for that character, move to it; otherwise create a new child node and move to it. After the last character, mark the node as the end of a word (is_end = True). Insertion takes O(L) time for a word of length L and creates at most L new nodes. Inserting the same word twice leaves the trie unchanged, unless you also track counts.

Read full answer

Applies tobuilding dictionaries for autocomplete, spell checking and prefix queries; LeetCode 208 "Implement Trie"

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()   # create the missing edge
            node = node.children[ch]
        node.is_end = True                       # mark the last node as a word end

    def search(self, word):
        node = self.root
        for ch in word:
            node = node.children.get(ch)
            if node is None:
                return False
        return node.is_end

t = Trie()
for w in ["cat", "car", "card", "care"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.search("card"))   # True False True
print(sorted(t.root.children["c"].children["a"].children))  # ['r', 't']

Step-by-Step: Inserting car, Then card

Step Character Action
1 c Root has no c: create it
2 a Create a under c
3 r Create r under a; mark is_end (word car)
4 (card) c, a, r All exist: just follow them
5 d Create d under r; mark is_end (word card)

Only one new node is created for card, because car already exists.

Variant: Counting Words and Prefixes

class CountingNode:
    def __init__(self):
        self.children = {}
        self.prefix_count = 0   # words that pass through this node
        self.word_count = 0     # words that end exactly here (supports duplicates)

def insert_counting(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, CountingNode())
        node.prefix_count += 1
    node.word_count += 1

root = CountingNode()
for w in ["apple", "app", "apple"]:
    insert_counting(root, w)
node = root
for ch in "app":
    node = node.children[ch]
print(node.prefix_count, node.word_count)   # 3 1

Variant: Fixed Array for Lowercase Letters

class ArrayNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

def insert_array(root, word):
    node = root
    for ch in word:
        i = ord(ch) - 97                         # 'a' -> 0
        if node.children[i] is None:
            node.children[i] = ArrayNode()
        node = node.children[i]
    node.is_end = True

r = ArrayNode(); insert_array(r, "hi")
print(r.children[ord("h") - 97] is not None)     # True

Complexity

Measure Cost
Time O(L)
New nodes At most L
Total space for n words O(total characters) nodes; with 26-slot arrays, O(total characters x 26) pointers in the worst case

Edge Cases

  • Empty string: marks the root as a word end; decide whether that should be allowed.

  • Normalisation: lowercase or casefold() before inserting if search should be case-insensitive.

  • Validation: with fixed arrays, reject characters outside the alphabet.

Interview Tip

Walk through the loop (follow or create a child, then mark the end), state O(L) time and at most L new nodes, and show how counts can be added. Mentioning duplicates and normalisation shows attention to edge cases.

11

How do you check whether a word is stored in a trie?

To search for a word, start at the root and follow the child for each character in order. If any character has no matching child, the word is not present. If you reach the end of the word, return whether the final node is marked is_end, because reaching a node only proves the word is a prefix of some stored word. Search takes O(L) time for a word of length L and O(1) extra space. A closely related function, starts_with(prefix), returns True as soon as the whole prefix is walked, without checking is_end.

Read full answer

Applies todictionary lookups, spell checking, autocomplete and LeetCode 208 "Implement Trie (Prefix Tree)"

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None          # path breaks: not in the trie
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

t = Trie()
for w in ["apple", "app", "bat"]:
    t.insert(w)
print(t.search("app"), t.search("appl"), t.search("apples"), t.search("bat"))
# True False False True
print(t.starts_with("appl"), t.starts_with("c"))   # True False

Three Possible Outcomes

Query Path exists? is_end at last node? Result
app Yes Yes Found
appl Yes No Not found (only a prefix)
apples No (no s after apple) Not found

Forgetting the is_end check is the most common bug: it makes every prefix look like a stored word.

Recursive Version

class TrieNode:
    def __init__(self):
        self.children, self.is_end = {}, False

def search_rec(node, word, i=0):
    if i == len(word):
        return node.is_end
    child = node.children.get(word[i])
    return child is not None and search_rec(child, word, i + 1)

root = TrieNode()
node = root
for ch in "go":
    node = node.children.setdefault(ch, TrieNode())
node.is_end = True
print(search_rec(root, "go"), search_rec(root, "g"))   # True False

The iterative version is preferred in Python because it avoids recursion overhead and depth limits for long keys.

Complexity

Function Time Extra space
search(word) O(L) O(1) iterative
starts_with(prefix) O(P) O(1)

The cost does not depend on the number of words stored.

Extensions

  • Case-insensitive search: normalise with casefold() at both insert and search time.

  • Wildcards (. matches any character): branch to all children at a wildcard position (LeetCode 211).

  • Return a value: store a payload (definition, ID, frequency) at end nodes to use the trie as a map.

  • Count matches: store prefix counts to return how many words share the prefix.

Interview Tip

Show the walk, explain that a missing child means “not found” and that is_end separates words from prefixes, and contrast search with starts_with. Mentioning wildcard search as an extension shows you are ready for follow-up questions.

12

How do you delete a word from a trie?

Deleting a word has two steps. First, find the word and unmark is_end on its last node, so the word no longer exists. Second, prune nodes that are no longer needed: walking back from the end towards the root, remove each node that has no children and is not the end of another word, and stop at the first node that is still needed (because another word passes through it or ends there). If the word is not in the trie, nothing changes. Deletion takes O(L) time.

Read full answer

Applies todynamic dictionaries, autocomplete indexes with removals, routing tables (route withdrawal) and blocklists

Cases to Handle

Situation Example (trie has car, card, cat) Result
Word is a prefix of another word Delete car Unmark r; keep it because card passes through
Word shares a prefix with others Delete card Remove d; stop at r because car ends there
Word has a unique tail Delete cat Remove t; stop at a (it still has child r)
Word not present Delete cow No change

Implementation in Python (Iterative, With a Path Stack)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            node = node.children.get(ch)
            if node is None:
                return False
        return node.is_end

    def delete(self, word):
        path, node = [], self.root               # (parent, char) pairs along the word
        for ch in word:
            child = node.children.get(ch)
            if child is None:
                return False                      # word not present
            path.append((node, ch))
            node = child
        if not node.is_end:
            return False                          # only a prefix, not a word
        node.is_end = False
        # prune from the bottom up while nodes are empty and not word ends
        for parent, ch in reversed(path):
            child = parent.children[ch]
            if child.children or child.is_end:
                break
            del parent.children[ch]
        return True

t = Trie()
for w in ["car", "card", "cat"]:
    t.insert(w)
print(t.delete("car"), t.search("car"), t.search("card"))    # True False True
print(t.delete("card"), "r" in t.root.children["c"].children["a"].children)   # True False
print(t.delete("cow"), t.search("cat"))                      # False True

After deleting car and then card, the whole r branch is gone; cat remains.

Recursive Version

class TrieNode:
    def __init__(self):
        self.children, self.is_end = {}, False

def delete_rec(node, word, i=0):
    """Returns True if `node` can be removed by its parent."""
    if i == len(word):
        if not node.is_end:
            return False
        node.is_end = False
        return not node.children
    child = node.children.get(word[i])
    if child is None:
        return False
    if delete_rec(child, word, i + 1):
        del node.children[word[i]]
        return not node.children and not node.is_end
    return False

root = TrieNode()
for w in ["to", "tea"]:
    n = root
    for ch in w:
        n = n.children.setdefault(ch, TrieNode())
    n.is_end = True
delete_rec(root, "tea")
print(sorted(root.children["t"].children))   # ['o']

Complexity

  • Time: O(L) to find the word plus O(L) to prune.

  • Space: O(L) for the path stack or recursion.

Variants and Practical Notes

  • Lazy deletion: only unmark is_end and skip pruning; it is simpler and faster, but leaves unused nodes (memory grows with churn). Periodic rebuilds can clean up.

  • Counting tries: decrement prefix counts along the path, and remove nodes whose count reaches zero.

  • Duplicate words: decrement a word count and unmark only when it reaches zero.

  • Radix trees: after deleting, a node left with a single child should be merged with that child to keep the tree compressed.

  • Concurrency: deletion modifies shared structure; use locks or copy-on-write for concurrent readers.

Interview Tip

Describe the two steps (unmark is_end, then prune empty non-end nodes bottom-up), walk through the cases where another word shares the path, and give O(L) complexity. Mentioning lazy deletion and the radix-tree merge step shows deeper understanding.

13

How does a trie compare with a binary search tree?

A trie organises strings by characters along a path, so search, insert and prefix queries cost O(L) for key length L, regardless of the number of keys. A binary search tree (BST) organises whole keys by comparison, so a balanced BST needs O(log n) comparisons, each of which may compare up to L characters, giving O(L log n) for strings. Tries win for prefix queries and large dictionaries with shared prefixes. BSTs are more general (any comparable keys), usually use less memory, and support range queries, rank and order statistics naturally.

Read full answer

Applies tochoosing ordered and string-keyed data structures in interviews and systems (dictionaries, indexes, symbol tables)

Comparison

Aspect Trie Balanced BST (AVL, red-black)
Key type Sequences (strings, bits, digits) Any comparable type
Search / insert / delete O(L) O(log n) comparisons, O(L log n) for strings in the worst case
Depends on number of keys? No Yes (log n)
Prefix search O(P + results), natural Possible as a range scan [prefix, prefix + max char), O(L log n + results)
Longest prefix match Natural single walk Awkward
Sorted iteration DFS in child order In-order traversal
Range queries (between two keys) Possible but less natural Natural
Order statistics (k-th key, rank) Needs subtree counts Natural with augmented nodes
Memory High: a node per character plus child maps One node per key with two pointers
Balance Shape fixed by the keys (depth = key length) Needs rebalancing (rotations)
Shared prefixes Stored once Stored in every key
Cache behaviour Pointer chasing per character Pointer chasing per comparison

Example: Prefix Query Both Ways

import bisect

words = sorted(["car", "card", "care", "cat", "dog", "door"])

# Sorted array (like a BST's in-order sequence): prefix search as a range scan
def prefix_range(sorted_words, prefix):
    lo = bisect.bisect_left(sorted_words, prefix)
    hi = bisect.bisect_left(sorted_words, prefix + "\uffff")
    return sorted_words[lo:hi]

# Trie: walk the prefix, collect the subtree
class Node:
    def __init__(self):
        self.children, self.is_end = {}, False

root = Node()
for w in words:
    n = root
    for ch in w:
        n = n.children.setdefault(ch, Node())
    n.is_end = True

def collect(node, path, out):
    if node.is_end:
        out.append(path)
    for ch in sorted(node.children):
        collect(node.children[ch], path + ch, out)
    return out

n = root
for ch in "car":
    n = n.children[ch]
print(prefix_range(words, "car"), collect(n, "car", []))
# ['car', 'card', 'care'] ['car', 'card', 'care']

Both work. The BST or sorted structure needs two O(L log n) searches; the trie needs one O(P) walk.

When to Choose a Trie

  • Autocomplete, spell checking, word games: frequent prefix queries.

  • Longest-prefix matching (routing, URL routers).

  • Huge dictionaries with heavily shared prefixes.

  • Keys over small alphabets (bits, DNA bases).

When to Choose a BST

  • Keys are not strings (numbers, dates, composite keys).

  • Range queries, floor and ceiling, k-th smallest, rank queries.

  • Memory matters more than prefix speed.

  • You already have a library sorted map (Java TreeMap, C++ std::map, Python sortedcontainers.SortedDict).

Interview Tip

Compare complexities precisely (O(L) vs O(L log n) for strings), highlight prefix and longest-prefix queries as the trie’s strengths, and range queries, generality and memory as the BST’s. Showing that a sorted structure can do prefix search as a range scan gives a nuanced answer.

14

How do you choose between a hash table and a trie?

Choose a hash table when you need fast exact-match lookups (is this key present, what is its value) with low memory use and simple code. Choose a trie when your queries depend on prefixes or ordering: autocomplete, “does any key start with X”, longest prefix match, counting keys by prefix, sorted iteration, or pruned searches in word games. Also consider data shape: tries pay off when keys share many prefixes and the alphabet is small; with random keys (UUIDs, hashes) a trie wastes memory for no benefit.

Read full answer

Applies todesigning dictionaries, caches, routing tables, autocomplete, spell checkers and symbol tables

Decision Guide

Question If yes
Only exact lookups, inserts and deletes? Hash table
Need all keys with a prefix, or prefix counts? Trie
Need longest prefix match (IP routes, URL routes)? Trie (radix or Patricia)
Need keys in sorted order? Trie or ordered tree, not a hash table
Memory is tight? Hash table (or a compressed or succinct trie)
Keys share few prefixes (random IDs)? Hash table
Need guaranteed worst-case time without hash collision risks? Trie (or a hash table with randomised hashing)
Searching a grid or text against many words with pruning? Trie

Side-by-Side

Aspect Hash table Trie
Exact lookup O(L) to hash plus O(1) average O(L)
Prefix query O(n x L) scan O(P + results)
Longest prefix Hash every prefix: up to L lookups One walk
Ordering None Lexicographic
Memory Lower Higher (nodes and child maps)
Worst case Degrades with collisions Stable O(L)
Implementation Built into every language Custom or a library

Example: Same Data, Different Questions

words = ["apple", "app", "application", "banana", "band", "bandana"]

# Hash set: perfect for exact membership
vocab = set(words)
print("band" in vocab, "ban" in vocab)              # True False

# Trie: perfect for prefix questions
class Node:
    def __init__(self):
        self.children, self.count = {}, 0

root = Node()
for w in words:
    n = root
    for ch in w:
        n = n.children.setdefault(ch, Node())
        n.count += 1

def prefix_count(p):
    n = root
    for ch in p:
        n = n.children.get(ch)
        if n is None:
            return 0
    return n.count

print(prefix_count("app"), prefix_count("ban"))     # 3 3

Hybrid Approaches

  • Hash map children inside a trie: flexible alphabets with prefix support.

  • Hash table plus sorted index: exact lookups in O(1) and prefix or range queries via a sorted array or tree.

  • Hash table of prefixes: for a fixed small set of prefix lengths, store each prefix in a hash map (common in routing implementations with a few distinct prefix lengths).

  • Search engines: inverted indexes (hash-like) for exact terms, with finite-state transducers (trie-like, as in Lucene) for term dictionaries and prefix or fuzzy queries.

Interview Tip

Frame the choice around query types: exact lookups favour hash tables, prefix, longest-prefix and ordered queries favour tries. Then factor in memory, key distribution and worst-case guarantees, and mention hybrids such as Lucene’s FST term dictionary to show real-world awareness.

15

What is a suffix trie, and how does it differ from a standard trie?

A suffix trie is a trie built from all suffixes of a single text. For banana, it stores banana, anana, nana, ana, na and a. Because every substring of the text is a prefix of some suffix, a substring search becomes a simple walk in O(m) for a pattern of length m. A standard trie stores a set of separate words for prefix and dictionary queries. The cost of a suffix trie is size: up to O(n^2) nodes for a text of length n, which is why practical systems use the compressed suffix tree (O(n) nodes, built in O(n) with Ukkonen’s algorithm) or the more compact suffix array.

Read full answer

Applies tosubstring search, bioinformatics (genome analysis), plagiarism and duplicate detection, data compression, and string algorithm interviews

Differences

Aspect Standard trie Suffix trie
Built from A collection of words All suffixes of one text
Main query Is this word present? Which words start with X? Does this pattern occur anywhere in the text?
Size O(total characters of all words) O(n^2) nodes for a text of length n
End markers Word ends (is_end) Suffix ends, often a $ terminator
Compressed form Radix tree Suffix tree

Building a Suffix Trie in Python

def build_suffix_trie(text):
    text += "$"                                  # unique end marker
    root = {}
    for i in range(len(text)):
        node = root
        for ch in text[i:]:
            node = node.setdefault(ch, {})
    return root

def contains(trie, pattern):
    node = trie
    for ch in pattern:
        if ch not in node:
            return False
        node = node[ch]
    return True

def count_occurrences(trie, pattern):
    node = trie
    for ch in pattern:
        if ch not in node:
            return 0
        node = node[ch]
    stack, leaves = [node], 0                    # each "$" leaf below is one suffix
    while stack:
        n = stack.pop()
        if "$" in n:
            leaves += 1
        stack.extend(child for ch, child in n.items() if ch != "$")
    return leaves

st = build_suffix_trie("banana")
print(contains(st, "nan"), contains(st, "nab"))                  # True False
print(count_occurrences(st, "ana"), count_occurrences(st, "a"))  # 2 3

The $ terminator ensures no suffix is a prefix of another, so each suffix ends at its own leaf; counting leaves under the pattern’s node counts its occurrences.

What Suffix Structures Answer

Query How
Is pattern P a substring? Walk P: O(m)
Count occurrences of P Count leaves under P’s node
Longest repeated substring Deepest internal node with two or more leaves
Longest common substring of two strings Build over S1#S2$; deepest node with leaves from both
Number of distinct substrings Number of nodes (excluding the root and terminator paths) in the suffix trie

From Suffix Trie to Suffix Tree and Suffix Array

Structure Size Build time Notes
Suffix trie O(n^2) O(n^2) Simple; only for short texts
Suffix tree O(n) nodes (edges store index ranges) O(n) with Ukkonen’s algorithm Fast queries; high constant memory factor
Suffix array (+ LCP array) O(n) integers O(n log n) simple, O(n) with SA-IS Compact; pattern search in O(m log n)
FM-index Compressed, near text size O(n) Used in genome aligners (BWA, Bowtie)

Interview Tip

Explain that a suffix trie stores all suffixes so that substring search becomes a prefix walk, contrast it with a word-set trie, and point out the O(n^2) size. Mentioning suffix trees (Ukkonen, O(n)) and suffix arrays as the practical forms shows depth.

16

How does a compressed trie or radix tree improve on a standard trie?

A compressed trie, usually called a radix tree or Patricia trie, merges chains of single-child nodes into one edge labelled with a string. In a standard trie, the word international alone creates 13 nodes, one per character. In a radix tree, a path with no branching becomes a single edge, so the number of nodes is bounded by the number of keys (a tree with n keys has at most about 2n nodes) rather than the total number of characters. Lookups still take O(L) character comparisons, but with far fewer nodes, pointers and memory accesses. That makes radix trees the standard choice for routing tables, in-memory indexes and HTTP routers.

Read full answer

Applies toIP routing (Patricia and LC-tries), web routers (Go's `httprouter`, Echo), database indexes (adaptive radix trees), Redis (`rax` for streams), Linux kernel radix trees (page cache, now the XArray)

Standard Trie vs Radix Tree

Words: romane, romanus, romulus, rubens, ruber

Radix tree:
(root)
 └── "r"
      ├── "om"
      │    ├── "an"
      │    │    ├── "e"   (romane)
      │    │    └── "us"  (romanus)
      │    └── "ulus"     (romulus)
      └── "ub"
           ├── "ens"      (rubens)
           └── "er"       (ruber)

A standard trie would need one node per character on each branch (19 nodes including the root); the radix tree needs 10.

Implementation Sketch in Python

class RadixNode:
    def __init__(self):
        self.edges = {}        # first char -> (label, child)
        self.is_end = False

class RadixTree:
    def __init__(self):
        self.root = RadixNode()

    def insert(self, word):
        node = self.root
        while word:
            first = word[0]
            if first not in node.edges:
                leaf = RadixNode(); leaf.is_end = True
                node.edges[first] = (word, leaf)
                return
            label, child = node.edges[first]
            k = 0                                     # common prefix length
            while k < len(label) and k < len(word) and label[k] == word[k]:
                k += 1
            if k == len(label):                       # edge fully matched: descend
                node, word = child, word[k:]
                continue
            mid = RadixNode()                          # split the edge at k
            mid.edges[label[k]] = (label[k:], child)
            node.edges[first] = (label[:k], mid)
            if k == len(word):
                mid.is_end = True
            else:
                leaf = RadixNode(); leaf.is_end = True
                mid.edges[word[k]] = (word[k:], leaf)
            return
        node.is_end = True

    def search(self, word):
        node = self.root
        while word:
            entry = node.edges.get(word[0])
            if entry is None:
                return False
            label, child = entry
            if not word.startswith(label):
                return False
            node, word = child, word[len(label):]
        return node.is_end

    def count_nodes(self):
        stack, n = [self.root], 0
        while stack:
            node = stack.pop(); n += 1
            stack.extend(child for _, child in node.edges.values())
        return n

rt = RadixTree()
words = ["romane", "romanus", "romulus", "rubens", "ruber"]
for w in words:
    rt.insert(w)
print(rt.search("romanus"), rt.search("roman"), rt.search("ruber"))   # True False True
print(rt.count_nodes())                                                # 10

The tree has 10 nodes including the root, compared with 19 in a character-per-node trie for the same words.

Benefits

Benefit Explanation
Fewer nodes At most about 2n nodes for n keys, independent of key length
Less memory Fewer node objects, child maps and pointers
Fewer memory hops Each edge consumes several characters at once, which improves cache behaviour
Great for long keys with shared prefixes URLs, file paths, IP prefixes
Same capabilities Prefix search, longest prefix match, sorted iteration

Costs and Complexity

  • Insertion and deletion are more complex: edges must be split on insert and merged after delete when a node is left with one child and is not a word end.

  • Edge labels take memory; implementations often store (offset, length) references into the original keys.

  • Lookup is still O(L) character comparisons, but with fewer node visits.

Notable Variants

  • Patricia trie (binary radix tree): stores only the bit index where keys differ; used in routing.

  • Adaptive radix tree (ART): chooses node sizes of 4, 16, 48 or 256 children based on fan-out, giving fast and compact in-memory database indexes.

  • Multibit and level-compressed tries: consume several bits per step for IP lookups.

Interview Tip

Explain the compression of single-child chains into string-labelled edges, quantify the node savings (bounded by the number of keys, not characters), and describe how insertion splits edges and deletion merges them. Naming real users (routers, HTTP routers, ART, Redis) shows practical knowledge.

17

How do you find the longest common prefix of strings using a trie?

Insert every string into a trie, then walk down from the root while the current node has exactly one child and is not the end of a word. Every character on that walk is shared by all strings. The walk stops at the first branch (two or more children) or at a node where some string ends, and the characters collected so far form the longest common prefix (LCP). Building the trie costs O(S) for S total characters, and the walk costs at most the length of the shortest string.

Read full answer

Applies toLeetCode 14 "Longest Common Prefix", file path and URL grouping, autocomplete grouping, and DNA sequence analysis

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def longest_common_prefix(strs):
    if not strs:
        return ""
    root = TrieNode()
    for s in strs:
        if s == "":
            return ""                        # an empty string means no common prefix
        node = root
        for ch in s:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    prefix, node = [], root
    while len(node.children) == 1 and not node.is_end:
        ch, node = next(iter(node.children.items()))
        prefix.append(ch)
    return "".join(prefix)

print(repr(longest_common_prefix(["flower", "flow", "flight"])))     # 'fl'
print(repr(longest_common_prefix(["interview", "internet", "interval"])))   # 'inter'
print(repr(longest_common_prefix(["dog", "racecar", "car"])))        # ''
print(repr(longest_common_prefix(["app", "apple"])))                 # 'app'

Why Both Stopping Conditions Matter

  • Branching: in flower, flow, flight, after fl the node has children o and i, so the prefix stops at fl.

  • Word end: in app, apple, the node after app has one child (l) but app ends there; continuing would give appl, which is not a prefix of app.

Trace for ["flower", "flow", "flight"]

Node Children is_end Action
root f No Take f
f l No Take l
l o, i No Two children: stop

Result: fl.

Complexity

Step Cost
Build the trie O(S) time and space, S = total characters
Walk O(m), m = length of the shortest string

Simpler Alternatives (for a One-Off Query)

import os

def lcp_vertical(strs):
    if not strs:
        return ""
    for i, ch in enumerate(strs[0]):
        if any(i >= len(s) or s[i] != ch for s in strs[1:]):
            return strs[0][:i]
    return strs[0]

def lcp_sorted(strs):
    if not strs:
        return ""
    a, b = min(strs), max(strs)          # the lexicographically extreme pair decides it
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return a[:i]

words = ["flower", "flow", "flight"]
print(lcp_vertical(words), lcp_sorted(words), os.path.commonprefix(words))   # fl fl fl

Vertical scanning uses O(1) extra space, so it is usually preferred for a single LCP query. The trie approach pays off when the set changes or you need many prefix queries on the same data, such as the LCP of each group or prefix counts.

Interview Tip

Build the trie, then walk while there is exactly one child and no word ends, and explain why both conditions are needed using the app and apple example. Mentioning vertical scanning or the min/max trick as simpler options for a single query shows good judgement.

18

How do you count the total number of words stored in a trie?

To count the words in a trie, traverse every node and count those with is_end = True, using DFS or BFS, which takes O(N) for N nodes. If the count is needed often, maintain it incrementally: keep a word_count in the trie (or a prefix_count in each node), increment it when an insert marks a new word end, and decrement it on delete. Then the total is the root’s count, available in O(1), and the number of words with any prefix can be read in O(P).

Read full answer

Applies todictionary statistics, autocomplete indexes, prefix-count queries (LeetCode 1804 "Implement Trie II") and interview problems

Approach 1: Traversal

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    node.is_end = True

def count_words(root):
    count, stack = 0, [root]
    while stack:
        node = stack.pop()
        count += node.is_end
        stack.extend(node.children.values())
    return count

root = TrieNode()
for w in ["cat", "car", "card", "care", "cat"]:      # "cat" twice: still one word
    insert(root, w)
print(count_words(root))                            # 4

The iterative stack avoids recursion limits on long words.

Approach 2: Maintained Counters (O(1) Total, O(P) per Prefix)

class Node:
    def __init__(self):
        self.children = {}
        self.ends = 0          # how many times a word ends here (supports duplicates)
        self.passing = 0       # how many stored words pass through this node

class CountingTrie:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        node = self.root
        node.passing += 1
        for ch in word:
            node = node.children.setdefault(ch, Node())
            node.passing += 1
        node.ends += 1

    def erase(self, word):
        if self.count_exact(word) == 0:
            return
        node = self.root
        node.passing -= 1
        for ch in word:
            child = node.children[ch]
            child.passing -= 1
            if child.passing == 0:
                del node.children[ch]            # prune the now-unused branch
                return
            node = child
        node.ends -= 1

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def total(self):
        return self.root.passing

    def count_exact(self, word):
        n = self._walk(word)
        return n.ends if n else 0

    def count_prefix(self, prefix):
        n = self._walk(prefix)
        return n.passing if n else 0

t = CountingTrie()
for w in ["apple", "apple", "app", "apply"]:
    t.insert(w)
print(t.total(), t.count_exact("apple"), t.count_prefix("app"))   # 4 2 4
t.erase("apple")
print(t.total(), t.count_exact("apple"), t.count_prefix("appl"))  # 3 1 2

Which to Use

Approach Total count Prefix count Update cost Memory
Traversal O(N) O(subtree size) None None extra
Maintained counters O(1) O(P) O(L) per insert or delete Two integers per node

Distinct vs Total Words

Decide whether duplicates count:

  • Distinct words: count nodes with is_end (or ends > 0).

  • Total insertions: sum ends across nodes, or read root.passing in the counting trie.

Interview Tip

Give the traversal (count is_end nodes) with O(N) cost, then the maintained-counter design for O(1) totals and O(P) prefix counts, including how delete updates counts. Clarifying whether duplicates should be counted shows attention to requirements.

19

How do you list all words with a given prefix stored in a trie?

To list all words with a prefix, walk from the root along the prefix’s characters. If any character is missing, no words match. Otherwise, run a DFS from the prefix node, building each path’s string and collecting it whenever a node has is_end = True. Visiting children in sorted order returns the words lexicographically. The cost is O(P + size of the subtree). For large result sets, stop after k results, or precompute top-k at nodes, as autocomplete systems do.

Read full answer

Applies toautocomplete, command completion, search-as-you-type, contact lookup and dictionary browsing

Implementation in Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def words_with_prefix(self, prefix, limit=None):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return []
        results = []
        stack = [(node, prefix)]
        while stack:
            n, path = stack.pop()
            if n.is_end:
                results.append(path)
                if limit is not None and len(results) == limit:
                    break
            for ch in sorted(n.children, reverse=True):   # reversed so pops come out sorted
                stack.append((n.children[ch], path + ch))
        return results

t = Trie()
for w in ["car", "card", "care", "careful", "cat", "dog"]:
    t.insert(w)
print(t.words_with_prefix("car"))            # ['car', 'card', 'care', 'careful']
print(t.words_with_prefix("ca", limit=3))    # ['car', 'card', 'care']
print(t.words_with_prefix("z"))              # []

Pushing children in reverse sorted order onto a stack makes them pop in sorted order, so the iterative DFS yields lexicographic results, and the limit lets it stop early.

Generator Version (Lazy Results)

class TrieNode:
    def __init__(self):
        self.children, self.is_end = {}, False

def iter_words(node, path):
    if node.is_end:
        yield path
    for ch in sorted(node.children):
        yield from iter_words(node.children[ch], path + ch)

root = TrieNode()
for w in ["tea", "ten", "to"]:
    n = root
    for ch in w:
        n = n.children.setdefault(ch, TrieNode())
    n.is_end = True

from itertools import islice
print(list(islice(iter_words(root.children["t"], "t"), 2)))   # ['tea', 'ten']

Generators let callers take just the first few results without exploring the whole subtree.

Complexity

Part Cost
Walk the prefix O(P)
Collect results O(number of nodes in the subtree) for all results; less with a limit
Output size Sum of the lengths of the returned words

Building path strings by concatenation adds copying cost. A shared character list with append and pop (backtracking) avoids it for very long words.

Scaling Up

  • Top-k per node: store the k most popular completions at each node, making queries O(P + k).

  • Ranking: store frequencies at end nodes and use a heap to choose the best k instead of the first k alphabetically.

  • Pagination: resume a DFS from a saved position (the last returned word) for “load more”.

  • Compressed tries: fewer nodes to visit for long shared prefixes.

Interview Tip

Describe walking to the prefix node, then a DFS collecting is_end nodes, give O(P + subtree) complexity, and show how sorted children give lexicographic order. Adding the limit or generator and the top-k optimisation shows you think about real autocomplete workloads.

20

How do you solve word search in a grid using a trie?

To find many dictionary words in a letter grid (LeetCode 212 “Word Search II”), insert all the words into a trie, then start a DFS from every cell, moving to adjacent cells while following the matching trie child. If the current letter has no child in the trie, stop immediately, since no word continues that way. When you reach a node that stores a word, record it. Marking cells as visited during the DFS prevents reuse within one word. The trie lets one traversal search for all words at once, sharing work across common prefixes, which is far faster than running a separate search for each word.

Read full answer

Applies toBoggle and word-game solvers, puzzle generators, and backtracking interview problems

Implementation in Python

class TrieNode:
    __slots__ = ("children", "word")
    def __init__(self):
        self.children = {}
        self.word = None            # the full word stored at its end node

def find_words(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.word = w

    rows, cols = len(board), len(board[0])
    found = []

    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent.children.get(ch)
        if node is None:
            return                                  # prune: no word continues this way
        if node.word:
            found.append(node.word)
            node.word = None                        # avoid duplicates
        board[r][c] = "#"                           # mark visited
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                dfs(nr, nc, node)
        board[r][c] = ch                            # restore
        if not node.children and node.word is None:
            del parent.children[ch]                 # prune exhausted branches

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return sorted(found)

board = [list("oaan"), list("etae"), list("ihkr"), list("iflv")]
print(find_words(board, ["oath", "pea", "eat", "rain"]))   # ['eat', 'oath']

Key Optimisations

Optimisation Effect
Trie of all words One DFS per cell finds every word instead of one search per word
Stop when no trie child Cuts off hopeless paths immediately
Store the whole word at its end node No need to rebuild strings along the path
Clear word after finding it No duplicate results; no repeated work
Delete exhausted trie branches Later searches skip parts of the trie that cannot produce new words
In-place visited marking (#) No extra visited set

Complexity

  • Building the trie: O(S) for S total characters in the words.

  • Search: worst case O(R x C x 4 x 3^(L-1)) for words up to length L: from each cell, 4 first moves, then at most 3 (you cannot go back). Pruning makes typical cases much faster.

  • Space: O(S) for the trie plus O(L) recursion depth.

Why Not Search Each Word Separately?

Running the single-word Word Search for each of W words costs about W times the work, and repeats the same prefixes over and over. With thousands of words, the trie approach is orders of magnitude faster, because the grid is explored once per starting cell and the shared prefix oa is explored only once for oath, oat and oak.

Variants

  • Eight-direction movement (Boggle): add diagonal moves.

  • Minimum word length or scoring: filter or score when recording words.

  • Very large dictionaries: pre-filter words whose letters are not all present on the board.

Interview Tip

Explain building a trie from the words, running DFS from every cell guided by the trie, pruning when there is no child, and backtracking with visited marks. Mentioning the de-duplication and branch-deletion optimisations is what separates a strong answer.

21

How does a trie reduce the time needed to search for words?

A trie cuts search cost by making lookups depend on the length of the query, not on the size of the dataset. Checking a word or a prefix takes O(L) steps, whether the trie holds a hundred words or ten million, because each character narrows the search to one branch. Compared with scanning a list (O(n x L)) or comparing against sorted keys (O(L log n)), it removes the dependence on n entirely for exact and prefix lookups. More importantly, it shares work across many queries or patterns: a single walk answers “which words start with this prefix”, and trie-guided searches (grids, multi-pattern text matching) prune whole groups of words at once.

Read full answer

Applies todictionaries, autocomplete, spell checking, multi-pattern matching (Aho-Corasick), grid word search, IP routing

Complexity Comparison

Operation Unsorted list Sorted array / BST Hash set Trie
Exact lookup O(n x L) O(L log n) O(L) average O(L)
Any word with prefix P? O(n x P) O(P log n) O(n x P) O(P)
All words with prefix P O(n x L) O(P log n + output) O(n x L) O(P + subtree)
Longest stored prefix of a query O(n x L) O(L log n) per candidate length O(L) hashes of L prefixes, O(L^2) total O(L)
Find all dictionary words in a text O(n x text) naive O(text + matches) with Aho-Corasick

Where the Savings Come From

  1. Branching narrows the candidates: after reading ca, only words starting with ca remain, with no comparisons against dog or zebra.

  2. Shared prefixes are processed once: inter, internal and internet share the first five steps.

  3. Early termination: a missing child proves that no stored word has that prefix.

  4. Batch queries: one structure answers many related queries, such as each keystroke in autocomplete extending the previous walk by one step.

Example: Prefix Queries at Scale

import random, string, time

random.seed(0)
words = ["".join(random.choices(string.ascii_lowercase, k=8)) for _ in range(200_000)]

root = {}
for w in words:
    node = root
    for ch in w:
        node = node.setdefault(ch, {})
    node["$"] = True

def trie_has_prefix(p):
    node = root
    for ch in p:
        node = node.get(ch)
        if node is None:
            return False
    return True

queries = ["".join(random.choices(string.ascii_lowercase, k=4)) for _ in range(200)]

t0 = time.perf_counter()
a = [trie_has_prefix(q) for q in queries]
t1 = time.perf_counter()
b = [any(w.startswith(q) for w in words) for q in queries]
t2 = time.perf_counter()
print(a == b, (t2 - t1) > 10 * (t1 - t0))   # True True

The trie answers each query in a few steps; scanning checks up to 200,000 words per query. Absolute timings vary by machine, but the gap grows with the dataset.

Multi-Pattern Search in Text

To find occurrences of thousands of keywords in a document, the Aho-Corasick algorithm builds a trie of the keywords plus failure links, then scans the text once in O(text length + matches), instead of searching for each keyword separately. It is used in intrusion detection systems, malware signature scanning and grep -F with many patterns.

Trade-offs

  • Memory: tries use more memory than hash sets or sorted arrays.

  • Build time: O(total characters) up front.

  • Exact lookups only: a hash set is usually as fast or faster and simpler.

Interview Tip

Explain that trie operations cost O(L) independent of n, compare with list, sorted and hash approaches in a table, and stress the bigger wins: prefix queries, shared prefixes, pruning and multi-pattern search with Aho-Corasick. Acknowledging the memory cost keeps the answer balanced.

22

What space optimisations can be applied to a trie?

Trie memory can be reduced at three levels. Per node: store children in a dict, sorted array or bitmap instead of a fixed 26- or 256-slot array, use __slots__ or packed structs, and keep only the fields you need. Per structure: compress single-child chains (radix or Patricia trees), share common suffixes (DAWGs, minimal automata), or use ternary search trees. Per representation: for static dictionaries, encode the trie into arrays (double-array tries, LOUDS succinct tries, FSTs) that use close to the theoretical minimum of bits. Memory pools and integer indices instead of pointers also cut per-node overhead.

Read full answer

Applies tolarge dictionaries, autocomplete indexes, spell checkers, routing tables, search engines (Lucene's FST term dictionary) and mobile or embedded applications

Optimisation Catalogue

Technique Saves Trade-off
Dict or hash-map children Unused slots in sparse nodes Slightly slower child lookup than arrays
Sorted array of (char, child) pairs Hash-table overhead O(log k) lookup; slower inserts
Bitmap plus packed child array One bit per possible child, children stored compactly Popcount to index; more complex updates
Adaptive node sizes (ART: 4, 16, 48, 256) Space for small nodes, speed for large ones Node type changes as fan-out grows
Radix / Patricia compression Nodes on non-branching paths Edge splitting and merging logic
Suffix sharing (DAWG, minimal automaton) Duplicate suffixes like -ing, -tion Static or harder to update; no per-word data without extra work
Ternary search tree Wide child arrays Extra comparisons per character
Double-array trie Pointer overhead Hard to update dynamically
Succinct trees (LOUDS) Pointers replaced by bit vectors (about 2 bits per node plus labels) Slower navigation; static
Integer indices into a node pool 64-bit pointers become 32-bit indices Fixed maximum size; manual memory management
Store edge labels as (offset, length) into the keys Duplicate label strings in radix trees Must keep the original keys

Python Illustration: Dict Children and __slots__

import sys

class FatNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class SlimNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}
        self.is_end = False

fat, slim = FatNode(), SlimNode()
print(sys.getsizeof(fat.children) > sys.getsizeof(slim.children))   # True
print(hasattr(fat, "__dict__"), hasattr(slim, "__dict__"))         # True False

__slots__ removes the per-instance __dict__, and an empty dict is smaller than a 26-slot list. For millions of nodes, these savings add up.

Suffix Sharing Example

Words walking, talking, walked, talked: a trie stores -alking and -alked twice (once under w, once under t). A DAWG merges identical sub-trees, so the shared tails exist once. Spell-checker dictionaries and word-game engines use this to fit large vocabularies in a few megabytes.

Static Dictionaries: Compact Encodings

  • Double-array trie: transitions stored in two integer arrays (base and check); lookups are fast array accesses (used by MeCab and other tokenisers).

  • LOUDS / succinct tries: tree shape as a bit string with rank and select support (marisa-trie in Python).

  • Finite state transducers (FSTs): share prefixes and suffixes and can map keys to values; Lucene stores its term dictionary this way.

Practical Tips

  • Measure before optimising: Python object overhead often dominates, so a C-backed library (marisa-trie, datrie, pygtrie for convenience) may beat hand-tuning.

  • For mostly static data, build once and convert to a compact form.

  • Keep payloads (frequencies, IDs) in separate arrays indexed by node or word ID rather than in every node.

  • Use byte-level tries on UTF-8 for large Unicode alphabets to keep fan-out at most 256.

Interview Tip

Organise the answer by node-level (dict, sorted arrays, bitmaps, __slots__), structural (radix compression, DAWGs, ternary trees) and representation-level (double-array, succinct, FST) optimisations, with their trade-offs. Mentioning real users like Lucene’s FST or marisa-trie shows practical awareness.

23

What is memory pooling, and how can it make trie operations faster?

Memory pooling means allocating many objects of the same size from a pre-allocated block (a pool or arena) instead of calling the general-purpose allocator for each one. For a trie, which creates huge numbers of small, identical nodes, a pool makes allocation almost free (bump a pointer or pop a free list), stores nodes contiguously for better cache locality, lets nodes refer to each other by small integer indices instead of 64-bit pointers, and allows freeing the whole trie at once. The result is faster inserts, faster traversals, and lower memory overhead.

Read full answer

Applies toC, C++, Rust and Go implementations of tries, radix trees and other node-heavy structures; also array-based tries in Python and Java

Why Tries Benefit

Problem with per-node allocation Pool solution
One malloc/new per node is slow (allocator bookkeeping, locks or thread caches) Allocation is an index increment or free-list pop
Allocator headers add bytes per node Nodes packed back to back
Nodes scattered in memory: cache misses on each step Nodes created together sit together
64-bit pointers per child 32-bit indices into the pool halve child-link size
Freeing millions of nodes one by one is slow Release the whole pool in one operation
Garbage collector pressure (Java, Go) Few large arrays instead of millions of objects

Index-Based Pool in Python

class PooledTrie:
    """Nodes live in parallel arrays; a node is just an integer index."""
    def __init__(self):
        self.children = [{}]          # children[i]: char -> node index
        self.is_end = [False]
        self.free = []                # indices of deleted nodes for reuse

    def _new_node(self):
        if self.free:
            i = self.free.pop()
            self.children[i].clear(); self.is_end[i] = False
            return i
        self.children.append({})
        self.is_end.append(False)
        return len(self.is_end) - 1

    def insert(self, word):
        node = 0
        for ch in word:
            nxt = self.children[node].get(ch)
            if nxt is None:
                nxt = self._new_node()
                self.children[node][ch] = nxt
            node = nxt
        self.is_end[node] = True

    def search(self, word):
        node = 0
        for ch in word:
            node = self.children[node].get(ch)
            if node is None:
                return False
        return self.is_end[node]

t = PooledTrie()
for w in ["tree", "trie", "try"]:
    t.insert(w)
print(t.search("trie"), t.search("tr"), len(t.is_end))   # True False 8

Eight nodes (root plus 7) live in two lists. In C, C++ or Rust, the same layout uses arrays of fixed-size structs, which is where the speed gains are largest.

Pool Design in Systems Languages

typedef struct {
    uint32_t child[26];   /* 0 means "no child"; index 0 is reserved */
    uint8_t  is_end;
} Node;

typedef struct {
    Node    *nodes;
    uint32_t used, capacity;
} Pool;

uint32_t pool_alloc(Pool *p) {
    if (p->used == p->capacity) {          /* grow geometrically */
        p->capacity *= 2;
        p->nodes = realloc(p->nodes, p->capacity * sizeof(Node));
    }
    memset(&p->nodes[p->used], 0, sizeof(Node));
    return p->used++;
}

Because children are indices, growing the pool with realloc does not invalidate links, which raw pointers would.

Trade-offs

Benefit Cost
Fast allocation and bulk free Memory is reserved even when not yet used
Better locality and smaller links Fixed node size; variable-size nodes need several pools
Lower GC pressure Manual reuse logic (free lists) for deletions
Easy serialisation (arrays can be written to disk directly) Index limits (for example 2^32 nodes)

When It Matters

  • Building tries with millions of keys (dictionaries, routing tables, n-gram models).

  • Short-lived tries built per request or per batch and discarded together (arenas).

  • Memory-mapped or serialised tries loaded directly from disk.

Interview Tip

Define memory pooling, explain why tries (many small, identical nodes) benefit (fast allocation, locality, compact indices, bulk free), and show an index-based layout. Pointing out that indices survive pool reallocation, unlike pointers, shows practical systems knowledge.

24

How would you serialise and deserialise a trie?

The simplest way to serialise a trie is a pre-order DFS that writes, for each node, its end-of-word flag, its number of children, and then each child’s character followed by that child’s encoding. Deserialising reads the same sequence back recursively (or with a stack) to rebuild the identical tree. Alternatives: store the word list and re-insert (simple and robust), use a nested JSON structure (readable), or write a compact array or succinct format (double-array, LOUDS, FST) that can be memory-mapped and queried without rebuilding. Each takes O(N) for N nodes.

Read full answer

Applies tosaving autocomplete indexes, shipping dictionaries with apps, caching built tries between runs, and LeetCode-style "serialise a tree" problems

Approach 1: Pre-Order Encoding

Format per node: is_end, child count, then (char, child) pairs, using a token list or a compact string.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, TrieNode())
    node.is_end = True

def serialize(root):
    out = []
    stack = [root]
    while stack:
        node = stack.pop()
        if isinstance(node, str):          # a character marker
            out.append(node)
            continue
        out.append("1" if node.is_end else "0")
        out.append(str(len(node.children)))
        for ch in sorted(node.children, reverse=True):
            stack.append(node.children[ch])
            stack.append(ch)               # popped first: char precedes its subtree
    return " ".join(out)

def deserialize(data):
    tokens = iter(data.split(" "))
    def build():
        node = TrieNode()
        node.is_end = next(tokens) == "1"
        for _ in range(int(next(tokens))):
            ch = next(tokens)
            node.children[ch] = build()
        return node
    return build()

def words(node, prefix=""):
    out = [prefix] if node.is_end else []
    for ch in sorted(node.children):
        out += words(node.children[ch], prefix + ch)
    return out

root = TrieNode()
for w in ["to", "tea", "ten", "i", "in"]:
    insert(root, w)
data = serialize(root)
print(data)
# 0 2 i 1 1 n 1 0 t 0 2 e 0 2 a 1 0 n 1 0 o 1 0
print(words(deserialize(data)))   # ['i', 'in', 'tea', 'ten', 'to']

Space-separated tokens assume characters are not spaces; for arbitrary text, use length-prefixed fields or a binary format.

Approach 2: Word List

Serialise just the stored words (with any counts or values), then rebuild by inserting them. It is format-agnostic, robust to code changes, and compresses well, but rebuilding costs O(total characters).

Approach 3: Nested JSON

import json

def to_obj(node):
    obj = {c: to_obj(ch) for c, ch in sorted(node.children.items())}
    if node.is_end:
        obj["$"] = 1
    return obj

class N:
    def __init__(self):
        self.children, self.is_end = {}, False

r = N()
for w in ["go", "gone"]:
    n = r
    for ch in w:
        n = n.children.setdefault(ch, N())
    n.is_end = True
print(json.dumps(to_obj(r), separators=(",", ":")))
# {"g":{"o":{"n":{"e":{"$":1}},"$":1}}}

Readable and easy to debug, but verbose; the key $ must not collide with real characters.

Approach 4: Compact Binary or Array Formats

  • Flattened arrays: assign each node an index in BFS order and write arrays of (first child index, child count, label, flags). These can be memory-mapped and searched directly.

  • Double-array tries and succinct LOUDS tries (marisa-trie supports save and mmap), and FSTs (Lucene) store large dictionaries in a few bytes per key.

Comparison

Format Size Load cost Notes
Pre-order tokens Medium O(N) rebuild Exact structure; simple
Word list Small (compresses well) O(total characters) rebuild Most robust
Nested JSON Large O(N) parse Human-readable
Flattened arrays / succinct / FST Smallest Near zero with mmap Best for large static dictionaries

Practical Considerations

  • Versioning: include a format version and the normalisation rules (case folding) in the header.

  • Payloads: serialise per-word data such as frequency or IDs alongside the flags.

  • Encoding: use UTF-8 and length prefixes for multi-character or binary labels.

  • Integrity: add a checksum when files are shipped or cached.

  • Deep tries: use iterative serialisation and deserialisation to avoid recursion limits.

Interview Tip

Present the pre-order encoding (flag, child count, labelled children) with a matching recursive reader, then mention alternatives: a word list, JSON, and compact memory-mappable formats. Discussing versioning, payloads and recursion depth shows production thinking.

25

How do you build a trie that supports '?' and '*' wildcard matching?

Store the words in a normal trie, then match a pattern with a DFS over (trie node, pattern position). A literal character follows its one child. ? matches exactly one character, so it tries every child. * matches zero or more characters: it either skips itself (zero characters) or consumes one child and stays on the * (one or more). A word matches when the pattern is used up at a node marked is_end. Memoising (node, index) pairs avoids exponential blow-up when patterns contain several stars, and the trie prunes any branch that cannot match.

Read full answer

Applies tofile-name globbing, search filters, crossword and word-game helpers, and interview problems (LeetCode 211 with `.`, extended to `*`)

Implementation in Python

class TrieNode:
    __slots__ = ("children", "word")
    def __init__(self):
        self.children = {}
        self.word = None                       # full word at its end node

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.word = word

    def match(self, pattern):
        results, seen = [], set()

        def dfs(node, i):
            key = (id(node), i)
            if key in seen:
                return
            seen.add(key)
            if i == len(pattern):
                if node.word is not None:
                    results.append(node.word)
                return
            p = pattern[i]
            if p == "*":
                dfs(node, i + 1)                        # '*' matches zero characters
                for child in node.children.values():
                    dfs(child, i)                       # '*' consumes one, stays active
            elif p == "?":
                for child in node.children.values():
                    dfs(child, i + 1)                   # exactly one character
            else:
                child = node.children.get(p)
                if child:
                    dfs(child, i + 1)

        dfs(self.root, 0)
        return sorted(set(results))

wt = WildcardTrie()
for w in ["cat", "cart", "card", "care", "cot", "coat", "dog"]:
    wt.insert(w)
print(wt.match("c?t"))     # ['cat', 'cot']
print(wt.match("car?"))    # ['card', 'care', 'cart']
print(wt.match("c*t"))     # ['cart', 'cat', 'coat', 'cot']
print(wt.match("*o*"))     # ['coat', 'cot', 'dog']
print(wt.match("c*"))      # ['card', 'care', 'cart', 'cat', 'coat', 'cot']

How * Works

At a *, two moves are possible:

  1. Zero characters: advance the pattern index and stay at the same trie node.

  2. One more character: move to any child and keep the pattern index on *.

Together, these let * absorb any number of characters. The seen set ensures each (node, index) state is explored once, so the total work is bounded by O(trie nodes x pattern length) instead of growing exponentially with the number of stars.

Complexity

Pattern type Work
Only literals O(L)
Literals and ? Up to O(alphabet^k) branches for k question marks, pruned by the trie’s actual children
With * and memoisation O(N x m) states for N trie nodes and pattern length m

Optimisations

  • Collapse consecutive stars (** to *) before matching.

  • Leading literal prefix: walk it directly before starting the DFS (car* jumps straight to the car node).

  • Length bounds: if a pattern has no *, only words of exactly its length can match; store depth or length information at nodes to prune.

  • Suffix trie or reversed-word trie: for patterns like *ing, search a trie of reversed words for gni* to avoid exploring the whole trie.

  • Limit results for interactive use.

Interview Tip

Explain the DFS over (node, pattern index), the handling of ? (any one child) and * (skip, or consume one and stay), and why memoisation keeps star patterns polynomial. Mentioning collapsing stars and reversed tries for suffix patterns shows optimisation thinking.

26

How would you build a trie-backed subsequence index for fast text search?

To check quickly which query words appear as subsequences of a text (characters in order, not necessarily adjacent), combine two structures. First, a next-occurrence index over the text: for each character, a sorted list of its positions, or a next-position table, so you can jump to “the next c after position i” in O(log n) or O(1). Second, a trie of the query words. A DFS over the trie carries the current text position and, for each child character, jumps to its next occurrence. If there is none, the whole subtree is pruned. Words that share a prefix share the work, so checking thousands of words costs about O(trie nodes x log n) instead of rescanning the text for every word.

Read full answer

Applies to"number of matching subsequences" problems (LeetCode 792), fuzzy command matching (typing `gco` to match `git checkout`), file-finder fuzzy search, and keyword filters over logs

Building the Index

from bisect import bisect_left
from collections import defaultdict

class SubsequenceIndex:
    def __init__(self, text):
        self.positions = defaultdict(list)          # char -> sorted list of indices
        for i, ch in enumerate(text):
            self.positions[ch].append(i)

    def next_pos(self, ch, start):
        """Smallest index >= start where text[index] == ch, or -1."""
        lst = self.positions.get(ch)
        if not lst:
            return -1
        k = bisect_left(lst, start)
        return lst[k] if k < len(lst) else -1

    def is_subsequence(self, word):
        pos = 0
        for ch in word:
            p = self.next_pos(ch, pos)
            if p < 0:
                return False
            pos = p + 1
        return True

Trie of Queries Plus Shared Traversal

from bisect import bisect_left
from collections import defaultdict

class SubsequenceIndex:
    def __init__(self, text):
        self.positions = defaultdict(list)
        for i, ch in enumerate(text):
            self.positions[ch].append(i)

    def next_pos(self, ch, start):
        lst = self.positions.get(ch)
        if not lst:
            return -1
        k = bisect_left(lst, start)
        return lst[k] if k < len(lst) else -1

class Node:
    __slots__ = ("children", "words")
    def __init__(self):
        self.children, self.words = {}, []

def matching_subsequences(text, queries):
    index = SubsequenceIndex(text)
    root = Node()
    for q in queries:
        node = root
        for ch in q:
            node = node.children.setdefault(ch, Node())
        node.words.append(q)

    found, stack = [], [(root, 0)]          # (trie node, next text position to search from)
    while stack:
        node, pos = stack.pop()
        found.extend(node.words)
        for ch, child in node.children.items():
            p = index.next_pos(ch, pos)
            if p >= 0:                       # otherwise prune this entire subtree
                stack.append((child, p + 1))
    return sorted(found)

text = "abcdefghijklmnopqrstuvwxyz" * 2
queries = ["ace", "acez", "zyx", "bdf", "bdfz", "aa", "qq", "zzz"]
print(matching_subsequences(text, queries))
# ['aa', 'ace', 'acez', 'bdf', 'bdfz', 'qq']

zyx fails because after the first z (index 25) the next y is at index 50, and no x follows it. zzz fails because there are only two zs. The prefixes ac and bdf are checked only once even though two queries share each of them.

Why It Is Fast

Approach Cost for W words of length up to L, text length n
Scan the text for each word O(W x n)
Next-occurrence lists, per word O(W x L x log n)
Trie of words plus next-occurrence lists O(trie nodes x log n); shared prefixes counted once, failed prefixes pruned
Next-position table (n x alphabet) O(1) jumps, so O(trie nodes); costs O(n x alphabet) memory

Greedy is correct: jumping to the earliest next occurrence of each character never hurts, because it leaves the most text for the remaining characters.

Streaming Alternative (“Waiting Buckets”)

For one pass over a very long text, keep buckets keyed by the next needed character, each holding (trie node) entries. For each text character c, advance every entry in bucket c to its children and re-bucket them by their next characters. This processes the text once, in O(n + total transitions), and suits streams.

Extensions

  • Ranking fuzzy matches: score by gaps between matched positions (smaller gaps and matches at word starts score higher), as fuzzy file finders do.

  • Multiple documents: build one index per document, or an inverted index from characters to (document, position) lists.

  • Updates: the trie of queries can change freely; rebuild the text index when the text changes.

Interview Tip

Explain the next-occurrence index (positions plus binary search, or a next-position table), the greedy earliest-jump argument, and how a trie of queries shares prefix work and prunes failures. Mentioning the streaming bucket approach for long texts shows depth.

27

How do you design a trie with efficient insert, search and startsWith?

An efficient trie uses a node with a children map and an is_end flag, plus a shared walk helper that follows characters from the root. insert walks and creates missing children, then marks the last node; search walks and returns True only if the path exists and ends at an is_end node; startsWith returns True if the path exists. All three run in O(L) time for a key of length L, independent of the number of stored words. Use a dict of children for flexible alphabets and sparse nodes, or a 26-slot array when keys are lowercase letters and speed matters most. Iterative code avoids recursion overhead.

Read full answer

Applies toLeetCode 208 "Implement Trie (Prefix Tree)", autocomplete back ends, dictionary services and interview design questions

Implementation in Python

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}
        self.is_end = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            nxt = node.children.get(ch)
            if nxt is None:
                nxt = node.children[ch] = TrieNode()
            node = nxt
        node.is_end = True

    def _walk(self, s: str):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

trie = Trie()
trie.insert("apple")
print(trie.search("apple"), trie.search("app"), trie.startsWith("app"))   # True False True
trie.insert("app")
print(trie.search("app"))                                                # True

Design Decisions

Decision Options Recommendation
Child storage Dict, 26-array, sorted list Dict for general use; array for lowercase-only hot paths
Node memory Plain class vs __slots__ __slots__ saves memory per node in Python
Shared logic Separate loops vs one _walk helper One helper avoids duplicated bugs
Iterative vs recursive Either Iterative: no recursion limit, less overhead
Extra data Counts, values, top-k lists Add only what queries need

Array-Based Variant (Lowercase a-z)

class ArrayTrie:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    def insert(self, word):
        node = self
        for ch in word:
            i = ord(ch) - 97
            if node.children[i] is None:
                node.children[i] = ArrayTrie()
            node = node.children[i]
        node.is_end = True

    def _walk(self, s):
        node = self
        for ch in s:
            node = node.children[ord(ch) - 97]
            if node is None:
                return None
        return node

    def search(self, word):
        n = self._walk(word)
        return n is not None and n.is_end

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

at = ArrayTrie()
at.insert("leet")
print(at.search("leet"), at.startsWith("le"), at.search("lee"))   # True True False

Array indexing avoids hashing but allocates 26 slots per node, which multiplies memory for sparse tries.

Complexity

Operation Time Space
insert O(L) O(L) new nodes at most
search O(L) O(1)
startsWith O(P) O(1)
Total O(total characters) nodes; x 26 pointers with arrays

Making It Production-Ready

  • Input validation and normalisation (case folding, allowed characters).

  • Deletion with pruning, and counts for prefix statistics.

  • Thread safety: a lock for writers, or build-then-swap immutable tries for read-heavy services.

  • Persistence: serialise to disk or build from a word list at startup.

  • Compression: radix tree for long keys with shared prefixes.

Interview Tip

Write clean code with a shared _walk, explain the is_end difference between search and startsWith, and state O(L) per operation. Comparing dict and array children and mentioning production concerns like thread safety and compression shows strong design sense.

28

How can a trie be kept balanced, and what affects its balance?

A standard trie cannot be “balanced” by rotations the way a BST can, because its shape is fixed by the keys: a key of length L always sits at depth L, so lookup cost is O(L) whatever the insertion order. What people mean by a “balanced trie” is keeping paths short and nodes evenly used. You get there by compressing single-child chains (radix or Patricia trees), choosing the alphabet or stride (bits, bytes or multibit chunks) to trade depth against fan-out, adapting node sizes (adaptive radix trees), and, for ternary search trees, whose shape does depend on insertion order, inserting keys in a balanced (median-first) order or rebuilding periodically. The factors that affect balance are key length and distribution, shared prefixes, alphabet size and insertion order (for TSTs).

Read full answer

Applies totries, radix trees, ternary search trees, routing tables and string indexes

Factors Affecting Trie Shape

Factor Effect
Key length Depth equals key length in an uncompressed trie; long keys give long paths
Shared prefixes Long common prefixes (https://www.) create long single-child chains
Key distribution Skewed data (many keys under one prefix) makes some subtrees huge and others tiny
Alphabet / stride Small alphabet (bits) means deep and narrow; large stride (bytes or 8-bit chunks) means shallow and wide
Insertion order No effect on a standard trie; significant for ternary search trees
Deletions Can leave chains that should be merged in compressed tries

Technique 1: Path Compression (Radix / Patricia)

Merging single-child chains bounds the number of nodes by about 2n for n keys and removes long “unbalanced” chains caused by shared prefixes or long unique suffixes. Lookups still compare O(L) characters but visit far fewer nodes.

Technique 2: Choosing Depth vs Fan-Out

For 32-bit integer keys:

def trie_shape(bits=32, stride=1):
    depth = -(-bits // stride)               # ceil division
    fanout = 2 ** stride
    return depth, fanout

for s in (1, 4, 8, 16):
    print(s, trie_shape(stride=s))
# 1 (32, 2)
# 4 (8, 16)
# 8 (4, 256)
# 16 (2, 65536)

Larger strides make the trie shallower (fewer memory accesses) but nodes wider (more memory, more empty slots). Level-compressed tries (LC-tries) and adaptive radix trees choose stride or node size per node based on how full it is.

Technique 3: Balancing a Ternary Search Tree

A TST node has lo, eq and hi children; the lo and hi links form a BST over characters at each level, so sorted insertion makes it degenerate into a linked list. Insert in median-first order to balance it:

class TSTNode:
    __slots__ = ("ch", "lo", "eq", "hi", "end")
    def __init__(self, ch):
        self.ch, self.lo, self.eq, self.hi, self.end = ch, None, None, None, False

def insert(node, word, i=0):
    ch = word[i]
    if node is None:
        node = TSTNode(ch)
    if ch < node.ch:
        node.lo = insert(node.lo, word, i)
    elif ch > node.ch:
        node.hi = insert(node.hi, word, i)
    elif i + 1 < len(word):
        node.eq = insert(node.eq, word, i + 1)
    else:
        node.end = True
    return node

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.lo), height(node.eq), height(node.hi))

def balanced_order(sorted_words):
    if not sorted_words:
        return []
    mid = len(sorted_words) // 2
    return [sorted_words[mid]] + balanced_order(sorted_words[:mid]) + balanced_order(sorted_words[mid + 1:])

words = sorted(chr(c) for c in range(ord("a"), ord("p")))   # 15 single-letter keys
root_sorted = None
for w in words:
    root_sorted = insert(root_sorted, w)
root_bal = None
for w in balanced_order(words):
    root_bal = insert(root_bal, w)
print(height(root_sorted), height(root_bal))   # 15 4

Sorted insertion gives height 15 (a chain); median-first order gives height 4 (about log2 of 15). Alternatives include shuffling keys before insertion, periodic rebuilds, or using self-balancing rotations on the lo/hi links (as in balanced TST variants).

Technique 4: Handling Skewed Data

  • Hash or split very large subtrees (a top-level hash on the first few characters, then tries below), common in sharded autocomplete services.

  • Reverse keys if suffixes are more distinctive than prefixes (for example domain names stored as com.example.www).

  • Strip common prefixes (such as a fixed URL scheme) before insertion.

Interview Tip

Clarify that a standard trie’s depth is set by key length and cannot be rebalanced, then explain the real levers: path compression, stride and fan-out choices, adaptive node sizes, and median-first or randomised insertion for ternary search trees. The sorted-vs-balanced TST height example makes the point concrete.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 28 Trie Data Structure answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects