You already know why a trie beats a hash set for prefix queries — this section is about the mechanical choices that actually show up in interview code: how you represent a node's children, how you mark end-of-word, and the memory/speed trade-offs those choices carry in each language's runtime.
Language Verdict: Pros, Cons & Recommendation
dict.setdefault(ch, TrieNode()) gives an atomic get-or-create in one line- Plain
dict/{} handles any character set (Unicode, digits) with zero upfront sizing decisions ord(ch) - ord('a') makes the fixed-array variant just as quick to write as the dict variant__slots__ is a one-line fix if an interviewer pushes on per-node memory overhead
- Every dict-based node carries real per-instance overhead (object header plus a
__dict__ unless __slots__ is used, plus a sparse hash table) that adds up across a large trie - No built-in
Trie/Radix type, so every interview still starts from a blank TrieNode class
TrieNode[26] sits close to the memory-efficiency floor — one object header, one contiguous reference array, no hashingch - 'a' works directly since char participates in integer arithmetic, no conversion step neededHashMap<Character, TrieNode>.computeIfAbsent mirrors Python's setdefault when a hashed alphabet is genuinely needed- Explicit field declarations make a node's shape obvious at a glance, no dynamic-attribute surprises
HashMap<Character, TrieNode> boxes every char key to Character, real overhead outside the cached 0–127 range- The array form has no get-or-create shorthand — always an explicit
if (children[idx] == null) check
[26]*TrieNode is a natural, dense layout — no boxing, no hashing, zero-value slots are nilmap[byte]*TrieNode / map[rune]*TrieNode handles any alphabet without an upfront size decision- Struct fields are the layout: no per-instance
__dict__ tax, no Character boxing range over a map iterates only present children; the array form is a tight 0..25 loop
- A map field must be
make'd — writing to a nil map panics, an easy init miss - No
setdefault/computeIfAbsent — always an explicit nil-check then assign - Collecting words onto a
[]byte path hits Go's slice-aliasing gotcha unless you copy at the leaf
Map<string, TrieNode> preserves insertion order and has a real .size, cleaner semantics than a plain objectnew Array(26).fill(null) stays a dense, single-element-kind array that V8 indexes about as fast as Java's array form- Plain
{} children work fine for quick interview code with zero class-boilerplate ceremony
- No
setdefault/computeIfAbsent equivalent — always an explicit .has() check then .set(), never a one-liner charCodeAt(0) - 97 is one more indirection than Python's ord or Java's direct char arithmetic- Choosing between
Map and plain-object children is itself a decision with trade-offs (prototype pollution, key coercion) the other two languages don't force on you
Recommendation: No language ships a built-in trie. Python's dict.setdefault is the fastest correct one-liner under time pressure and the typical DSA default; Java's or Go's [26]*TrieNode array node is the leanest memory footprint. JS works fine but lacks a get-or-create shorthand in either form.
Coding Mechanics, Side by Side
The flexible, alphabet-agnostic option — works for any character set (Unicode, digits, mixed case) at the cost of per-node hash-table overhead.
class TrieNode:
def __init__(self):
self.children = {} # dict[str, TrieNode]
self.is_end = False
A plain dict keyed by single-character strings handles any character set with no upfront sizing decision. Each populated dict carries CPython's hash-table overhead (a sparse slot table, roughly ~64 bytes minimum even near-empty, growing in chunks) — fine for a handful of children, but it adds up across a trie with millions of nodes over a large dictionary.
The dense, low-overhead option for a small known alphabet (e.g. 26 lowercase letters) — O(1) access with no hashing, but wasteful once the alphabet gets large or sparse.
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.is_end = False
# indexing by character:
idx = ord(ch) - ord('a')
node.children[idx]
[None] * 26 preallocates a fixed-size list of references — cheap to allocate and index, but every node pays for all 26 slots even if it only ever has one child. ord(ch) - ord('a') is the standard index computation; get this arithmetic wrong (e.g. forgetting to handle uppercase) and you'll silently index out of range or collide characters.
Both children-representation options solve the same problem, and picking between them is a genuine design decision worth stating out loud in an interview:
- Fixed array (
[26], or [36] for alphanumeric, etc.): O(1) index with no hashing, best cache locality, and the lowest per-node memory footprint when the alphabet is small and every node tends to use a meaningful fraction of its slots. It's wasteful when the alphabet is large (e.g. full Unicode) or when most nodes only ever have one or two children — you're paying for 26 (or more) reference slots per node regardless of how many are actually used.
- dict / HashMap / Map /
map[byte]*Node: only pays for the children that actually exist, so it scales gracefully to large or sparse alphabets, at the cost of per-entry hashing overhead and (in Java) boxing costs for primitive-like keys. Go's map must be make'd (nil map panics on write).
For the classic "lowercase English words" interview trie, the array form is usually preferred (and faster) once you know the alphabet is fixed and small. For anything with a larger or unknown character set — Unicode text, mixed-case with digits and punctuation, etc. — the map form is the more defensible default.
Two idioms exist: a boolean flag on the node, or a sentinel key in the children map. The boolean flag is simpler, more explicit, and what interviewers expect by default.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False # boolean-flag idiom (preferred)
# alternative: sentinel-key idiom
class TrieNodeSentinel:
def __init__(self):
self.children = {}
def mark_end(self):
self.children['#'] = None # or a dedicated END_MARKER object
The boolean is_end flag is unambiguous and O(1) to check, and it's the form virtually every interview solution uses. The sentinel-key alternative (stuffing a special '#' key into the same dict as real children) saves one field per node but conflates two different concepts in one collection and complicates iteration (you now have to skip the sentinel when walking real children) — generally not worth it outside of niche memory-constrained scenarios.
class TrieNode:
__slots__ = ('children', 'is_end') # optional: trims per-instance overhead
def __init__(self):
self.children = {}
self.is_end = False
A dict-based Python trie node carries real overhead on two fronts: the object itself (a Python object header plus, by default, a __dict__ for instance attributes unless you use __slots__), and the children dict, which is a hash table with sparse slots even when nearly empty. Over a trie built from a large dictionary (hundreds of thousands of words), this adds up to meaningfully more memory than the equivalent Java array-based structure. Adding __slots__ (shown above) removes the per-instance __dict__ and is a legitimate answer if an interviewer pushes on memory optimization.
The core mechanical pattern: walk character by character, create a child node if it doesn't exist yet, descend into it, and mark the final node as end-of-word. The exact "create if missing" syntax is where the languages diverge.
def insert(root, word):
node = root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
dict.setdefault(key, default) atomically does "get if present, else insert-and-return the default" in one call — the idiomatic one-liner for this pattern. The equivalent explicit form (if ch not in node.children: node.children[ch] = TrieNode()) is more verbose but arguably more readable to someone unfamiliar with setdefault; either is acceptable in an interview. Note setdefault always constructs the TrieNode() default argument eagerly (even when not needed) since Python doesn't lazily evaluate arguments — negligible cost here, but worth knowing.
Same walk-the-characters shape as insert, but now failing fast (early return) the moment a required child is missing, instead of creating one.
def starts_with(root, prefix):
node = root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True
def search(root, word):
node = root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end
ch not in node.children is an O(1) average-case membership check on the dict. search differs from starts_with only in the final check (node.is_end) — a detail that's easy to forget under pressure and a common source of off-by-one-concept bugs (returning True for a prefix that was never inserted as a full word).
Needed for tasks like serializing a trie or DFS-ing all stored words. The map/dict form only iterates keys that actually exist; the array form has to skip empty slots.
def collect_words(node, path, results):
if node.is_end:
results.append(''.join(path))
for ch, child in node.children.items():
path.append(ch)
collect_words(child, path, results)
path.pop()
dict.items() iterates only the character keys that were actually inserted — no wasted iterations over absent children. This is the direct payoff of the dict/Map representation: iteration cost is proportional to the number of actual children, not the alphabet size.