templates · Heaps & tries

Trie (prefix tree)

  • Many words, and the questions are about prefixes: autocomplete, "starts with", shortest root
  • You search for lots of words in one go (a dictionary against a grid or a sentence)
  • Words share beginnings, so walking letter by letter saves repeated work

Trie (prefix tree)

the one rule

The invariant

The path from the root spells a prefix, and end is true only where a full inserted word stops.

write it from memory

The template

javajava.util.*
/** Prefix tree over lowercase words: insert, exact search and prefix search, each O(length). */class PrefixTree {    private static class Node {        final Node[] next = new Node[26];             // one slot per letter        boolean end;                                  // a word ends exactly here    }     private final Node root = new Node();     void insert(String word) {        Node cur = root;        for (char c : word.toCharArray()) {            int i = c - 'a';                          // letter → slot            if (cur.next[i] == null) cur.next[i] = new Node();            cur = cur.next[i];        }        cur.end = true;                               // mark the last node    }     boolean search(String word) {        Node node = walk(word);        return node != null && node.end;              // the path exists AND a word ends here    }     boolean startsWith(String prefix) {        return walk(prefix) != null;                  // the path alone is enough    }     /** Follows the letters from the root; null if the path breaks. */    private Node walk(String s) {        Node cur = root;        for (char c : s.toCharArray()) {            cur = cur.next[c - 'a'];            if (cur == null) return null;        }        return cur;    }}

Both searches share one walk helper. The only difference: search also checks end.

fill in the blanks — only these lines change per problem

  1. line 4The child slots. Node[26] for lowercase letters; use a HashMap<Character, Node> for any character, or Node[2] for bits.
  2. line 5What a node remembers. A boolean here; store the whole word, a count or an index when the problem needs it.
  3. line 13How a character becomes a slot number, e.g. c - 'a' or a bit (x >> b) & 1.
  4. line 22What counts as a hit. A full word needs end; a prefix question can stop as soon as the path exists.

complexity

What it costs

time O(L) per operation
insert, search and startsWith each walk one node per letter, L = length of the word. The number of stored words does not matter.
space O(total letters × 26)
At most one new node per inserted letter, and each node holds an array of 26 child slots.

watch out

Common bugs

  • Returning true from search just because the path exists. Without end, "app" is found after inserting only "apple".
  • Forgetting to mark end = true after the insert loop.
  • Using c - 'a' on input with capital letters or digits, which gives an index out of range.

use it

Practise it on

learn it properly