Basic Trie

Prefix Search (startsWith)

Exactly like search, but you don't need the 'end of word' marker. If you can follow all characters in the prefix without hitting a missing child, the prefix exists in the trie. Any words below that node share the prefix.

O(m)

O(1)

How It Works

Prefix search (startsWith) walks the trie exactly like a full word search: follow the child pointer for each character of the prefix in turn. The one difference is the ending condition — reaching the last character successfully is enough, with no need to check the end-of-word flag, because any node on a path is by construction a prefix of every word stored beneath it.

The query runs in O(P) for a prefix of length P, regardless of dictionary size — the property that makes tries irreplaceable. A hash set would need either O(n * P) scanning of all keys or precomputed storage of every prefix of every word, which explodes memory. Returning the node where the walk ends (rather than a boolean) is a useful generalization: the subtree below it contains precisely the words sharing that prefix, ready for counting or enumeration.

Step-by-Step Visualization

Check if prefix 'app' exists in trie

Followroot → a

1/2

Code

Java

static boolean startsWith(Trie trie, String prefix) {
  TrieNode node = trie.root;
  for (char ch : prefix.toCharArray()) {
    if (!node.children.containsKey(ch)) return false;
    node = node.children.get(ch);
  }
  return true; // Don't check isEnd!
}

Tips & Gotchas

1Same as search but don't check isEnd flag

2If you can follow all characters, the prefix exists

3Useful for autocomplete, word filtering

Practice Problems

1Implement Trie (Prefix Tree)
2Replace Words
3Map Sum Pairs
4Search Suggestions System

About the Basic Trie Pattern

Each node has up to 26 children (for lowercase letters). Insert by walking/creating nodes for each character. Search by walking the tree — if you can follow the entire word and the last node is marked as 'end', the word exists.

Key insight

Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.

Common Trie Interview Problems

Implement Trie
Word Search II
Design Add and Search Words
Replace Words
Maximum XOR of Two Numbers

Frequently Asked Questions

What is the only difference between search and startsWith in a trie?

The final check. Both walk the same character path and fail identically if a child is missing; search additionally requires the terminal node's end-of-word flag to be true, while startsWith accepts any successfully completed walk.

How can I count how many words share a given prefix efficiently?

Augment each node with a counter incremented on every insertion passing through it (and decremented on deletion). A prefix-count query then walks to the prefix node and reads the counter in O(P), avoiding any subtree traversal.