Get started

Trie Coding Problems: 6 Questions with Solutions

6 trie coding problems — 1 easy · 5 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 3-day plan.

  • Problems: 6
  • By difficulty: 1 easy · 5 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A trie, or prefix tree, stores a set of words one character per level, so words that share a prefix share the path that spells it. Asking whether any stored word starts with a given prefix, or which stored word is the shortest prefix of another, then costs the length of the word rather than the size of the dictionary. The same tree built over the bits of integers, highest bit first, answers maximum-XOR questions greedily. The problems here practise building the tree, marking where words end, and walking it alongside a second string.

How trie works, step by step

carttdogrootcarcatcartdogwords"car""cat""cart""dog"prefix "ca"→ car, cart, cat
Prefix search over words, with a trie. Example: insert "car", "cat", "cart", "dog"; find words starting with "ca"
  1. A trie stores words letter by letter along paths from the root, so words with the same beginning share their first nodes. Each node also records whether a word ends there, because a word can be the prefix of a longer one.
  2. Insert "car": the trie is empty, so c, a and r become a chain of new nodes from the root, and r is marked as the end of a word.
  3. Insert "cat": the walk reuses c and a from "car", since they share the prefix "ca", then adds t and marks it as the end of a word.
  4. Insert "cart": c, a and r already exist, because "car" is a prefix of "cart", so only t is new, hung below r. r keeps its own end mark, so "car" and "cart" are both words.
  5. Insert "dog": no stored word starts with d, so d, o and g are all new, a separate branch from the root, and g is marked as an end. A trie only shares what words really have in common.
  6. To find the words starting with "ca", walk from the root: c, then a, 2 steps however many words are stored. That node has no end mark, so "ca" is not a word itself, but everything below it starts with "ca".
  7. Collecting every end mark below that node gives "car", "cart" and "cat", and the "d" branch is never touched. Inserting or walking a word of length L costs O(L); listing the matches costs the size of that one subtree.

Trie study plan

All 6 Trie problems (1 easy and 5 medium) over 3 days, about 3 h 30 min in all — the pattern first, then easiest to hardest. Then move on to Backtracking.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Next topic: Backtracking

Trie: the essentials

When to reach for it

Many words and questions about their prefixes: does any stored word start with this, which root is the shortest prefix of this word, is every prefix of a word also a word. A whole-word lookup is a Hash Table job. Built over bits, highest first, a trie also finds the largest XOR of two numbers.

The pattern

Each node maps a character to a child and flags where a word ends. Insert walks the word, creating missing children, and flags the last node; search walks the same way and fails at the first missing child. Every node passed spells a prefix of the word, so the first flagged one is its shortest stored prefix.

def insert(trie, word):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})  # the child, created if missing
    node["$"] = True                    # a word ends here

def shortest_root(trie, word):          # shortest stored prefix, or None
    node = trie
    for i, ch in enumerate(word):
        node = node.get(ch, {})         # {} once the path runs out
        if "$" in node: return word[:i + 1]
    return None

Cost

O(L) per insert or search for a word of length L, however many words are stored, and at most one node per character inserted. A 26-slot array per node is faster than a dictionary and far larger.

Common mistakes

  • Taking a path for a word: "app" lies on the path of "apple" but is stored only if its node is flagged.
  • Checking the flag only at the end of the word, which misses every shorter root.
  • 26-slot arrays for 10⁵ words of length 100: up to 2.6 × 10⁸ slots.
  • Building a bit trie lowest bit first, when the highest differing bit decides an XOR.

Start with

All trie problems

Easy (1)

Medium (5)

Companies that ask trie problems

Next topic: Backtracking