Skip to content
Hello Python
Data Structure1 Practice4 Interview

Trie

Prefix tree for incremental string lookup, autocomplete, and dictionary-constrained search. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Trie when the prompt's constraints and required operations match this shape: Prefix tree for incremental string lookup, autocomplete, and dictionary-constrained search.

Pybit studies a professional Trie interview workspace with precise technical objects.
On this page · Mental Model

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Trie Code Labs

Mental Model

A trie stores one character per edge and shares nodes among words with the same prefix. Following the characters of a query reaches exactly its prefix node, if those edges exist.

Characters Label Edges

Represent each node as a dictionary from next character to child node. Insertion and lookup take O(L) expected time for a length-L string, independent of how many other words share the path. The dictionary contract(opens in a new tab) supplies expected constant-time edge lookup. Memory depends on stored characters and alphabet branching; sparse dictionaries avoid allocating a full alphabet array at every node.

Distinguish Prefix from Complete Word

Existing edges prove only that a prefix occurs. A terminal marker records that a stored word ends at this node, distinguishing app from the prefix of apple. The empty word, if allowed, marks the root terminal.

Separate Words from Prefixes

Reference
def trie_membership(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
        node[None] = True
    result = []
    for query in queries:
        node = root
        for character in query:
            if character not in node:
                node = None
                break
            node = node[character]
        result.append([node is not None and None in node, node is not None])
    return result
Practice

Implement trie_membership(words, queries). Return [is_word, is_prefix] for every query using explicit terminal markers.

Public tests

  • Verify word and prefix distinction

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Measure Shared Prefixes

For autocomplete or pruning, follow edges until the first missing character. The number traversed is the longest stored prefix path; it does not imply a complete-word match.

Measure Trie Prefix Paths

Reference
def trie_prefix_match_lengths(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
    lengths = []
    for query in queries:
        node = root
        matched = 0
        for character in query:
            if character not in node:
                break
            node = node[character]
            matched += 1
        lengths.append(matched)
    return lengths
Practice

Implement trie_prefix_match_lengths(words, queries). Return the number of query characters whose edges exist from the root.

Public tests

  • Verify partial shared prefixes

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Trie or Hash Set

Use a hash set for whole-word membership and a trie when prefixes, incremental character search, or dictionary-pruned backtracking dominate. Sorting strings can group prefixes compactly for offline work, while a trie supports repeated online queries.

Common Pitfalls

  • Omitting the terminal marker makes every prefix look like a word.
  • Creating child dictionaries during a read mutates the trie unexpectedly.
  • Copying prefix strings at every DFS node can add quadratic work.
  • A fixed alphabet array wastes space when the character domain is large or sparse.

Explain It in an Interview

Define what a node and terminal marker mean, then charge work to query characters. State the alphabet assumption and why prefix existence differs from word existence.

Follow Trie Edges(opens in a new tab) isolates path traversal; Implement Trie(opens in a new tab) adds complete insert, search, and prefix APIs.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Trie workflowO(total word characters + total query characters)O(total word characters + total query characters)A trie converts shared string prefixes into shared edges, so prefix traversal depends on query length rather than the number of stored words. After matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match.

Space

O(total word characters) for the demonstrated Trie workflow.

Assumptions

  • State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
  • The bound counts the operations in Follow Trie Edges and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Trie invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. A trie converts shared string prefixes into shared edges, so prefix traversal depends on query length rather than the number of stored words. This remains true after every accepted operation.
  3. After matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. This remains true after every accepted operation.

When To Use Or Avoid Trie

Use It When

  • Use Trie when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Trie invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def trie_prefix_match_lengths(words, queries):
    pass

Use instead

def trie_prefix_match_lengths(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
    lengths = []
    for query in queries:
        node = root
        matched = 0
        for character in query:
            if character not in node:
                break
            node = node[character]
            matched += 1
        lengths.append(matched)
    return lengths

Where you will hit this: Follow Trie Edges(opens in a new tab)

Breaking the central invariant

Checks only complete-word membership and ignores partial trie paths shared by longer stored words.

Prevent it: Keep this invariant visible while editing: State the precise Trie invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def trie_prefix_match_lengths(words, queries):
    word_set = set(words)
    return [len(query) if query in word_set else 0 for query in queries]

Use instead

def trie_prefix_match_lengths(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
    lengths = []
    for query in queries:
        node = root
        matched = 0
        for character in query:
            if character not in node:
                break
            node = node[character]
            matched += 1
        lengths.append(matched)
    return lengths

Where you will hit this: Follow Trie Edges(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(total word characters + total query characters).

Avoid

def trie_prefix_match_lengths(words, queries):
    word_set = set(words)
    return [len(query) if query in word_set else 0 for query in queries]

Use instead

def trie_prefix_match_lengths(words, queries):
    root = {}
    for word in words:
        node = root
        for character in word:
            node = node.setdefault(character, {})
    lengths = []
    for query in queries:
        node = root
        matched = 0
        for character in query:
            if character not in node:
                break
            node = node[character]
            matched += 1
        lengths.append(matched)
    return lengths

Where you will hit this: Implement Trie(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.