Sign in
Skip to solution
mediumDSA

What is a trie and when is it useful?

1.1k views
01

Understand the problem

Explain the trie data structure.

triestrings
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

A trie (prefix tree) stores strings by shared prefixes, with each node representing a character. It gives O(L) lookup/insert by word length L (independent of the number of words) — ideal for autocomplete, spell-checking, and prefix searches.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Trie: insert, search, startsWith
Run Playground
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True              # end-of-word marker

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

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

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node: return None
            node = node[ch]
        return node


# --- demo ---
t = Trie()
for w in ["cat", "car", "can"]:
    t.insert(w)
print(t.search("car"))        # True
print(t.search("ca"))         # False (prefix, not a full word)
print(t.starts_with("ca"))    # True
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 28 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track