Advanced Data Structures

Trie

Prefix tree for word lookup, prefix queries and autocomplete.

Hard, about 90 minutes to practise.

1Understand

The idea

A trie stores words character by character along paths from the root, so every word with the same prefix shares the same first nodes. Insert and search cost O(length of the word), whatever the number of words stored, and every word with a given prefix sits under one node.

Intuition

A trie stores words character by character along paths from the root, so words that share a prefix share those first nodes. Insert and search cost O(length), independent of how many words are stored.

Prefix search is the killer feature: every word with a given prefix sits under one node. Autocomplete, word search boards and XOR tries (bit tries) all use the same spine.

Mark word ends explicitly so "app" and "apple" can coexist.

What you will be able to do

  • Mark word ends explicitly
  • Combine a trie with DFS

When to use it

  • Many words sharing prefixes
  • startsWith queries
  • Word search with a dictionary

2See it

Walkthrough

Insert and search

Insert "app", search "app" / "ap".

1 / 5

i
a
p
p
012
i → index 0

node

  • ∅ empty

Root children empty. Create edge for "a".

node = root

Live template

Line 1 active

1class Node:
2 def __init__(self): self.children = {}; self.end = False
3def insert(word):
4 node = root
5 for ch in word: node = node.children.setdefault(ch, Node())
6 node.end = True

Complexity: time O(L) per op, space O(total chars)

Build O(total characters). Query O(length). Space can be large with sparse alphabets, nested dicts are fine in Python; fixed-size arrays of 26 win when the alphabet is tiny and dense. Hash sets find whole words but cannot share prefix structure.

Read the walkthrough as text

Insert and search. Insert "app", "apple", then search "app" and prefix "ap".

  1. From root, follow/create a → p → p, mark end on the third node.
  2. Insert "apple": reuse a-p-p, then add l → e and mark end.
  3. Search "app": walk three edges and check end flag, true.
  4. Prefix "ap": walk two edges, node exists, so some word has that prefix.

In code:

  • class Node:
  • def __init__(self):
  • self.children = {}
  • self.end = False

3Recognise it

Kinds of problems (6)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Insert / search / startsWith

    Example. Implement trie dictionary operations.

    How. Walk children dict per char; end flag marks complete words.

  • Wildcard search

    Example. Search with '.' matching any letter.

    How. DFS at node with branch all children on dot, else single char edge.

  • Word search II (trie + grid DFS)

    Example. Find all dictionary words in a grid.

    How. Trie of words; DFS grid pruning when prefix not in trie.

  • Autocomplete / top suggestions

    Example. Return top k words with prefix.

    How. Collect words under prefix node; sort by freq or heap k bests.

  • Longest common prefix

    Example. Longest shared prefix of word list.

    How. Walk trie until fork or word end; path chars form answer.

  • Binary trie over bits (maximum XOR)

    Example. Max XOR pair in array.

    How. Insert 32-bit bits; greedy opposite bit when available.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • No end marker

    Why it happens. Reaching node after last char means word exists.

    How it fails. search("app") true because "apple" was inserted, prefix mistaken for word.

    Fix. Insert sets node.is_end; search requires is_end true.

  • Rescanning the word list

    Why it happens. Linear scan word list for each prefix query is fine for small n.

    How it fails. Thousands of startsWith queries each scan whole dictionary, O(words·len) per query.

    Fix. Trie shares prefixes, one walk per query.

  • Found words not pruned

    Why it happens. DFS explores all paths even after word found.

    How it fails. Word search II revisits found words and duplicates in output.

    Fix. Mark trie word found and prune branch; or remove word from trie node.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons