Trees6 min read

Trie (Prefix Tree)

Store strings by their prefixes — autocomplete in \(O(L)\) time
insert: \(O(L)\)search: \(O(L)\)prefix search: \(O(L)\)space: \(O(total chars)\)

A trie (pronounced "try", from retrieval) is a tree where each node represents a character, and each path from root to a marked node spells out a word. All words that share a common prefix share the same path from the root.

Think of how a paper dictionary is organized: all words starting with "ca" are grouped together — "cat", "car", "card", "care". A trie makes this grouping explicit in the data structure itself.

Structure

Each trie node contains:

  • An array (or map) of up to 26 child pointers — one per letter of the alphabet
  • A boolean flag: is_end_of_word — marks that a complete word ends here
pseudocode
1
2
3
4
class TrieNode:
  def __init__(self):
    self.children = {}  # char → TrieNode
    self.is_end = False

The root represents the empty string — no character. Words are formed by following edges from parent to child, each edge labeled with a letter.

◈ Insert words

← → arrow keys to step · click elements to interact

Trie: Insert, Search & startsWith

class TrieNode:
    def __init__(self): self.children={}; self.is_end=False


class Trie:
    def __init__(self): self.root=TrieNode()
    def insert(self, word):
        n=self.root
        for c in word:
            if c not in n.children: n.children[c]=TrieNode()
            n=n.children[c]
        n.is_end=True
    def search(self, word):
        n=self.root
        for c in word:
            if c not in n.children: return False
            n=n.children[c]
        return n.is_end
    def starts_with(self, prefix):
        n=self.root
        for c in prefix:
            if c not in n.children: return False
            n=n.children[c]
        return True


t=Trie()
for w in ['cat','cats','car','card']: t.insert(w)
print(t.search('cat'))       # True
print(t.search('ca'))        # False (not a full word)
print(t.starts_with('ca'))   # True
print(t.starts_with('dog'))  # False
Output
True
False
True
False

Inserting a word

To insert "cat":

  1. Start at root. Does root have a child 'c'? If not, create one.
  2. Move to the 'c' node. Does it have child 'a'? If not, create one.
  3. Move to 'a' node. Does it have child 't'? If not, create one.
  4. Mark the 't' node as is_end = True.

Inserting "car" after "cat": steps 1-2 are shared (the 'c'->'a' path already exists), then at 'a' we add a new child 'r' and mark it as end. The shared prefix uses the same nodes — no duplication!

pseudocode
1
2
3
4
5
6
7
def insert(word):
  node = root
  for char in word:
    if char not in node.children:
      node.children[char] = TrieNode()
    node = node.children[char]
  node.is_end = True

Searching for a word

Follow the characters one by one. If any character is missing → word not in trie. If you reach the end of the word, check is_end.

pseudocode
1
2
3
4
5
6
def search(word):
  node = root
  for char in word:
    if char not in node.children: return False
    node = node.children[char]
  return node.is_end  # True only if a full word ends here

Prefix search (autocomplete)

The killer feature: check if any word starts with a given prefix in \(O(L)\) time, where L is the prefix length. Walk the prefix; if successful, every word reachable from that node is a valid completion.

pseudocode
1
2
3
4
5
6
def starts_with(prefix):
  node = root
  for char in prefix:
    if char not in node.children: return False
    node = node.children[char]
  return True  # valid prefix exists

When to use a trie

  • Autocomplete — search bars, IDE suggestions, spell checkers
  • Spell checking — store dictionary, check word existence in \(O(L)\)
  • IP routing tables — longest prefix matching
  • Word games — find all words with a given prefix instantly

Space consideration

Each node may store up to 26 child pointers (for lowercase English). For sparse character sets, a hash map is preferred over an array. The total space is \(O(total characters across all inserted words)\).

Note: A trie with 10,000 English words uses roughly 50,000–200,000 nodes due to shared prefixes. A hash set of the same words would use 10,000 entries but cannot do prefix search. It's a space-for-speed tradeoff.

Complexity

Insert word of length LOne step per character — no comparisons against other words
Fast\(O(L)\)
Search exact wordWalk L characters, check is_end flag
Fast\(O(L)\)
Prefix searchWalk prefix — all completions reachable from endpoint
Fast\(O(L)\)
Delete wordUnmark is_end; optionally prune unused nodes
Fast\(O(L)\)
SpaceShared prefixes save space vs. storing all words separately
Proportional\(O(total chars)\)

Count Words With Prefix

class TrieNode:
    def __init__(self): self.children={}; self.is_end=False; self.count=0


class Trie:
    def __init__(self): self.root=TrieNode()
    def insert(self, word):
        n=self.root
        for c in word:
            if c not in n.children: n.children[c]=TrieNode()
            n=n.children[c]
            n.count+=1   # count words passing through
        n.is_end=True
    def count_prefix(self, prefix):
        n=self.root
        for c in prefix:
            if c not in n.children: return 0
            n=n.children[c]
        return n.count


t=Trie()
for w in ['apple','app','application','apply','banana']: t.insert(w)
print(t.count_prefix('app'))  # 4
print(t.count_prefix('ban'))  # 1
print(t.count_prefix('xyz'))  # 0
Output
4
1
0
Challenge

Quick check

A trie contains the words: "app", "apple", "application". How many nodes does the prefix "appl" share across all three words?

Continue reading

Binary Trees
A family tree where every parent has at most two children
→
Binary Search Tree
A sorted binary tree — left is smaller, right is bigger
→
Suffix Array & LCP Array
Sort every suffix of a string — unlock powerful substring queries
→
Strings & FormattingPython
Slice, format, and play with text
→