How to implement a trie in Python: insert, search and startsWith

In this article

1. Before you start
2. Why interviewers ask this
3. Trie from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview patterns and method learning path. If you have not met a trie before, nothing else is required beyond three basics.

Why interviewers ask this

The question usually arrives as the LeetCode 208 task: a class with insert, search and startsWith methods. The problem statement as quoted describes a trie as a tree used to store and retrieve keys in a dataset of strings, with autocomplete and spellchecking as typical uses. Candidates report it, and variants such as a trie for file paths, in coding rounds.

It tests whether you can design a small data structure from nothing and keep three methods consistent. A weak answer returns true from search whenever the path exists. A strong answer explains why a path can exist only as the beginning of a longer word, and states the cost of each method in terms of word length. A Staff-level answer also names the memory cost and chooses between a dictionary and a fixed list for the children on purpose.

Trie from first principles

Trie

A trie, also called a prefix tree, is a tree that stores a set of strings one character per node, with the root holding no character, so that words sharing a beginning share the same path from the root.

Prefix

A prefix is the first few characters of a word, such as "da" for "dad"; the empty string and the whole word also count as prefixes of it.

In plain words

Picture a paper dictionary with thumb tabs. You open the tab for "d", then the section for "a", and everything there starts with "da". A trie turns that idea into a tree: each step down is one more letter, so finding a prefix means walking a path. The analogy breaks in one place. A paper dictionary lists each word once, while a trie has no list; words exist only as paths, and a flag marks which paths are complete words.

In one precise sentence, a trie gives every distinct prefix its own node. The only difference between search and startsWith is whether the final node must carry the flag.

The reason to build one is startsWith. AlgoMaster notes that a HashSet handles insert and search in constant time but has no answer for startsWith. Scanning a list or set instead costs time proportional to the number of words times their average length per call. In a trie, prefix lookups take time proportional to the prefix length, not the number of stored words.

Step 1: A node holds a children map and an end-of-word flag

A trie node is an object with two fields: a map from a character to the child node, and the end-of-word flag. The root is an ordinary node that stores no character, as GeeksforGeeks puts it: it acts as a starting point. In Python, children = {} (a undefined) is the usual map, and the flag starts as False. The name trie comes from Fredkin (1960), "Trie Memory"; René de la Briandais described the same kind of letter-by-letter tree in 1959. The trie class itself holds only the root.

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

class Trie:
    def __init__(self):
        self.root = TrieNode()  # the root holds no character

Input: nothing. Output: an empty trie, one node with no children. The first node you create has no letter on it; the letter lives on the edge, which is the dictionary key pointing to the child. Two Python designs exist: a dictionary like this one, or a fixed list of 26 slots per node as in the GeeksforGeeks version; the trade-offs section compares them.

Step 2: Insert walks the word and creates missing nodes

Insert walks the word one letter at a time from the root, creates a child wherever the letter is missing, and sets the end-of-word flag on the last node. The cost is one step per letter. Tutorial write-ups of this solution give insert as time proportional to the word length, written O(L), whatever the number of stored words.

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

Input: a word. Output: the trie now contains a path for it. Insert "and", then "ant": the second word reuses the nodes for "a" and "n" and adds only a new node for "t". That sharing is the whole point of the structure. Insert "dad" and the root gets a second branch. The next step reads the structure you just built.

Step 3: Search must check the end-of-word flag

Search walks the word's path and returns true only if the path exists and the final node's flag is set. A tutorial dry run inserts only "apple" and shows search("app") returning False, because the prefix exists but is not marked as a word, while startsWith("app") returns True. The flag check is the line candidates forget. A path can exist only because a longer word passed through it.

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

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

With "and", "ant" and "dad" stored, search("da") is false: the path exists, but the node after "a" under "d" has no flag. The buggy version, return node is not None, would say true. Input: a word. Output: a boolean. Search uses constant extra space, since it only follows existing nodes; the helper _walk is shared so the two read methods cannot drift apart.

Step 4: startsWith only needs the path to exist

The startsWith method returns true when the path for the prefix exists, ignoring the flag. The LeetCode problem statement says it returns true if a previously inserted string has that prefix; the same wording appears in a second-hand quote. The name startsWith is LeetCode's camelCase signature; idiomatic Python following the Python Enhancement Proposal (PEP) 8 style guide would write starts_with. Any inserted word that passes through a node proves the node's path is a prefix.

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

So startsWith("da") is true, search("da") is false, and search("dad") is true. The cost is again one step per letter of the prefix, and the extra space is constant. Finding every word under a prefix is one step further: walk to the prefix node, then traverse its subtree. You now have the whole structure: a node, three methods, and one flag that separates a word from a prefix.

1 · Root2 · Insert3 · Search4 · startsWithReplay

Step-by-step description

1. The root is a node that holds no character.
2. Insert adds one node per new letter and marks word ends.
3. Search da is false because the node has no flag.
4. startsWith da is true because the path exists.

• The root stores no character.
• Insert creates one node per new character and marks the last node as a word end.
• Search returns true only if the final node is marked as a word end.
• startsWith returns true if the path for the prefix exists.

Worked example

Run the three example words from the GeeksforGeeks page: "and", "ant" and "dad". Together they have nine letters, but the trie holds only seven character nodes, because "and" and "ant" share the path a, n. With the root that is eight nodes and seven parent-to-child links.¹ Sharing saved two nodes here, and the saving grows as more words overlap.

The bug is easy to show. After inserting only "apple", a version that ignores the flag answers true for search("app"), while the correct version answers false and startsWith("app") answers true.¹

For scale, take an illustrative list of 100,000 words, each eight letters long. Checking an eight-letter prefix by scanning compares about 800,000 characters in the worst case (100,000 words times eight letters), while a trie walks at most eight nodes.¹

Text description of the diagram

• A list of 26 slots per node uses 208 slots for the eight nodes.
• Dictionaries hold only the seven child entries that exist.

The chart shows why the child representation matters for memory: a list of 26 slots per node uses 208 slots for the eight nodes, against seven child entries in dictionaries.¹ A dictionary entry is bigger than one list slot, so the real saving is smaller than the slot ratio, but a sparse trie still favors dictionaries.

Trade-offs and edge cases

Memory is the main cost of a trie. AlgoMaster's comparison rates a trie's memory per word as higher than a hash map's, one node per character, and its space is proportional to the word length in the worst case, when no prefix is shared with existing words. A trie saves memory only when words overlap.

Text description of the diagram

• A set answers exact search but not startsWith.
• A trie answers startsWith in time proportional to the prefix length.

A hash lookup finds a whole word in constant time on average, so a trie is not faster for exact match; its advantage is prefix queries and walking words in order. Hashing a string also reads every letter, so the two are closer than they look.

Edge cases to handle: inserting the same word twice changes nothing; the empty string as a prefix makes _walk return the root, so this code returns True for startsWith("") even on an empty trie, which the LeetCode statement would call False (LeetCode's constraints rule out empty input, so it is worth a word to the interviewer, not extra code); and a word that is a prefix of another, such as "app" and "apple", needs the flag on an interior node.

The dictionary child map accepts any character, while a 26-slot list assumes lower-case letters and breaks on anything else. Another design choice is defaultdict, which removes the if ch not in check; the defaultdict page explains it. Other tree problems, such as the lowest common ancestor, use the same walk-and-return pattern.

How do you implement a trie tree for a file system?

A file-system trie is a trie whose keys are path segments, not letters. Split the path with path.strip("/").split("/"), let each node's children map a folder or file name to a child node, and replace the boolean with a value field. The rule interviewers check first: create(path, value) returns False when the path already exists or when its parent is missing, and get(path) returns the value, or -1 for an unknown path. Candidates report this variant in design-style rounds.

class PathNode:
    def __init__(self, value=None):
        self.children = {}
        self.value = value

class FileSystem:
    def __init__(self):
        self.root = PathNode()

    def create(self, path, value):
        parts = path.strip("/").split("/")
        node = self.root
        for name in parts[:-1]:            # every parent must exist
            node = node.children.get(name)
            if node is None:
                return False
        if parts[-1] in node.children:     # path already exists
            return False
        node.children[parts[-1]] = PathNode(value)
        return True

    def get(self, path):
        node = self.root
        for name in path.strip("/").split("/"):
            node = node.children.get(name)
            if node is None:
                return -1
        return node.value

On illustrative calls create("/a", 1), create("/a/b", 2), create("/c/d", 3), create("/a", 9), get("/a/b") and get("/c"), the script's results list is [true, true, false, false, 2, -1]: the third call fails because "/c" is missing, and the fourth because "/a" exists.² The sketch does not reject invalid input such as create("/", v) or an empty path, so mention that to the interviewer.

How to answer it in an interview

The spoken structure: say what a node holds, then insert, then why search needs the flag, then the cost. If you have time, name the dictionary-versus-list choice. The Python interview questions page covers the language details that tend to come up alongside it, and the trie ladder walkthrough takes the same idea to harder problems.

Common mistakes

• (wrong) "Search returns true if the path exists." The path can exist only as the start of a longer word. (right) "Search returns true only if the path exists and the last node's flag is set."
• (wrong) "The root stores the first letter." The root holds no character; letters sit on the links to children. (right) "The root is an empty starting node; its children are keyed by the first letters."
• (wrong) "A trie is always faster than a hash set." It is not faster for exact match. (right) "A trie wins on startsWith, which a hash set cannot answer without scanning."
• (wrong) "Operations get slower as I store more words." Each operation takes time proportional to the word or prefix length. (right) "Time depends on the word length; only memory depends on how many words and how much they overlap."
• (wrong) "A fixed list of 26 is always the better choice." It wastes slots on sparse nodes and fails on other characters. (right) "I use a dictionary unless the alphabet is small and the trie is dense."

Follow-up questions

What are the time and space complexity of a trie?

Insert, search and startsWith each take time proportional to the word or prefix length, and that does not depend on how many words are stored, as tutorial sources agree. Insert adds up to that many new nodes; search and startsWith use constant extra space.

Should the children be a dictionary or a list of 26?

A list of 26 gives direct indexing by letter and suits dense lower-case data. A dictionary stores only existing children and accepts any character, so it is the safer default in an interview. The trade is a little speed for flexibility.

Is a trie faster than a hash set?

Not for exact match, where a hash lookup is constant time on average. A trie is better when you need prefixes, such as autocomplete, because a hash set can answer startsWith only by scanning every word.

How do you delete a word from a trie?

The simple way is to clear the end-of-word flag on the last node. To free memory, walk back up and remove nodes that have no children and no flag of their own, stopping at the first node that is still needed.

How does a trie help in Word Search II?

A common approach builds a trie from the word list and then explores the board with depth-first search. A branch is abandoned the moment the letters so far are not a prefix of any word, which is exactly the check startsWith makes. The longest substring without repeating characters page shows a different string technique if you want to compare approaches.

Sources

1. Implement Trie (Prefix Tree), problem 208 (read 2026-10-26) — LeetCode, 26 Oct 2026
2. Trie Memory (Fredkin, Communications of the ACM 3(9):490-499) — Communications of the ACM, 1 Sep 1960
3. LeetCode 208, Implement Trie (Prefix Tree): problem statement as quoted — Medium (techsauce), quoting LeetCode, 16 Jun 2023
4. Trie Data Structure - Insert and Search — GeeksforGeeks, 26 Oct 2026
5. Implement Trie (Prefix Tree) — AlgoMaster.io, 26 Oct 2026
6. Introduction to Trie — AlgoMaster.io, 26 Oct 2026
7. Implement Trie (Prefix Tree): dictionary-based Python solution — Code and Debug, 26 Oct 2026
8. Built-in types: mapping types, dict — Python documentation, 26 Oct 2026