DevOps NetworkDevOpsNetwork
Join Free
Advanced

Implement Trie (Prefix Tree)

mediumTries Must-do

Problem statement

Build a class Trie that stores lowercase words and supports three operations:

  • insert(word) adds word to the store.
  • search(word) returns true only if exactly word was inserted before.
  • startsWith(prefix) returns true if any inserted word begins with prefix.

A trie (prefix tree) keeps words as paths of characters from a shared root, so every word with the same prefix shares the same first nodes. It is the structure behind autocomplete for CLI commands and hostnames, and behind prefix matching in routing tables.

Examples

Example 1

Input: insert("deploy"), search("deploy"), search("dep"), startsWith("dep")

Output: [true, false, true]

Explanation: dep is only a prefix of a stored word, not a stored word itself.

Example 2

Input: insert("log"), insert("login"), search("logi"), startsWith("logi"), search("log"), startsWith("x")

Output: [false, true, true, false]

Explanation: log is both a word and a prefix of login, so each node needs an end-of-word flag.

Hints

Approach

A real trie. Each node has children (character to node) and an end flag.

  • insert: walk from the root, creating a child for each missing character, and set end = True on the last node.
  • A helper walk(s) follows s character by character and returns the final node, or None if the path breaks.
  • search(word) is walk(word) exists and has end set; startsWith(prefix) is just walk(prefix) exists.

Every operation costs the length of its argument, no matter how many words are stored. In Java a fixed Node[26] array is faster than a map for lowercase letters.

ComplexityTime O(L) per operationSpace O(total characters inserted)
Python
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
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 startsWith(self, prefix):
return self._walk(prefix) is not None
t = Trie()
t.insert("deploy")
print([t.search("deploy"), t.search("dep"), t.startsWith("dep")])
t = Trie()
t.insert("log")
t.insert("login")
print([t.search("logi"), t.startsWith("logi"), t.search("log"), t.startsWith("x")])

Follow-up questions

  • Add countWordsStartingWith(prefix) in O(L) by storing a counter on each node.
  • Return the top 3 completions for a prefix, ranked by how often each word was inserted.

Frequently asked questions

Prefix lookups are core to infra systems: longest-prefix match in IP routing tables, path-based HTTP routers, key-prefix scans in etcd or other key-value stores, and shell or CLI autocomplete. A trie is the simplest structure that makes those lookups independent of how many keys are stored.

An array is faster and has no hashing cost, but reserves 26 slots per node even when most are empty. A dictionary uses memory only for real children and works for any alphabet. For lowercase-only input either is fine; say which you picked and why.

Walk to its last node and clear end. To reclaim memory, walk back up and remove child nodes that now have no children and are not the end of another word, usually with a recursive helper that reports whether a node became empty.