Coding interview problems › Design & Tries

🗃️ Design & Tries Medium

Implement Trie (Prefix Tree)

Implement Trie (prefix tree) explained: insert, search and startsWith in O(L) with child maps and an end-of-word flag, tested Python and a live visual.

Also searched as: trie implementation · prefix tree insert search startsWith · trie data structure interview question

🌲

Try it live Free

Trie & Autocomplete

Watch words branch into the trie, see shared prefixes reused, and type a prefix to list every completion in O(L), not O(dictionary).

Also useful: Hash Tables

Open the playground →

The problem

Build a prefix tree with three operations: insert(word), search(word) (was this exact word inserted?) and starts_with(prefix) (was any inserted word starting with this prefix?).

Inputinsert("apple"); search("apple"); search("app"); starts_with("app"); insert("app"); search("app")
OutputTrue, False, True, True

The key insight

A trie stores words as paths of characters from a root. Words that share a beginning share the same nodes, so a prefix is stored once. Each node holds a map from character to child plus a flag saying "a word ends here". Every operation walks one node per character, so its cost depends on the word length, not on how many words are stored.

Brute force first: Keeping words in a list makes starts_with O(total characters); a hash set handles search but cannot answer prefix queries efficiently.

Step-by-step approach

  1. Create a TrieNode with a children dictionary and an end flag.
  2. insert: start at the root; for each character, create the child if missing and move to it; finally set end = True.
  3. Write a helper _walk(s) that follows the characters and returns the last node, or None if a character is missing.
  4. search(word): the walk must succeed and the final node must have end set.
  5. starts_with(prefix): the walk only needs to succeed.

Python solution

PYTHON 3tested
class TrieNode:
    __slots__ = ("children", "end")

    def __init__(self):
        self.children = {}            # char -> TrieNode
        self.end = False              # a word ends at this node


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.end = True

    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 search(self, word):
        node = self._walk(word)
        return node is not None and node.end

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

Complexity

TimeO(L) per operation
SpaceO(total characters)

Each operation visits one node per character of its argument (L characters). In the worst case, with no shared prefixes, the trie holds one node per inserted character.

Common mistakes

Frequently asked questions

What is the time and space complexity of a trie?

Insert, search and startsWith each take O(L) time for a string of length L. Space is O(total characters inserted) in the worst case, and less when words share prefixes.

Should trie children be an array or a hash map?

An array of 26 is fast and simple for lowercase English letters. A dictionary uses less memory for sparse nodes and works for any character set. Both give O(L) operations.

How do I list all words with a given prefix (autocomplete)?

Walk to the prefix's node, then do a DFS from it, building the characters along the way and recording a word whenever a node's end flag is set.

How do I delete a word from a trie?

Walk to the word and clear its end flag. Optionally, on the way back up, remove nodes that have no children and are not the end of another word.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Design & Tries LRU Cache (HashMap + Linked List) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.