Lesson 19.1 · Trie

Building a Trie

Each node has up to 26 children (one per letter) and a flag marking the end of a word. Insert and search walk one node per character.

14 min

Think of it like this

A phone's contact list with a letter index: tap C, then A, and you see only the names starting with "CA". Each tap narrows the list without scanning every contact.

1.Shared prefixes

The root is empty. Each edge is a letter. A word is a path from the root, and the node where it ends has isWord = true. The flag matters: after inserting "cart", the path c → a → r exists, but "car" is only a word if it was inserted itself.

With lowercase English letters, Node[] next = new Node[26] is fast and simple; for larger alphabets use a HashMap<Character, Node>.

Rendering diagram…

Main.java

public class Main {
    static int nodes = 0;

    static class Node {
        Node[] next = new Node[26];
        boolean isWord;
        Node() { nodes++; }
    }

    static Node root = new Node();

    static void insert(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
            n = n.next[c - 'a'];
        }
        n.isWord = true;
    }

    static Node walk(String s) {
        Node n = root;
        for (char c : s.toCharArray()) {
            n = n.next[c - 'a'];
            if (n == null) return null;
        }
        return n;
    }

    public static void main(String[] args) {
        for (String w : new String[]{"car", "cat", "cart", "dog"}) insert(w);
        Node a = walk("car"), b = walk("ca");
        System.out.println("search car: " + (a != null && a.isWord));
        System.out.println("search ca: " + (b != null && b.isWord));
        System.out.println("startsWith ca: " + (b != null));
        System.out.println("nodes (without root): " + (nodes - 1));
    }
}

Output

search car: true
search ca: false
startsWith ca: true
nodes (without root): 8

2.Searching "cart" step by step

Search follows one child per character. If a child is missing, the word (and every word with that prefix) isn't there.

▶ Dry run: search("cart")trie has car, cat, cart, dog

↑i

path(list)

rootc

Step 1/4root has a child for c: move to it.

Remember

Insert and search cost O(L) for a word of length L.
The end-of-word flag separates words from prefixes.
Memory: up to 26 pointers per node.

Common mistakes

Returning true for a prefix that was never inserted as a word.
Allocating a 26-slot array for alphabets that aren't lowercase letters.

Words used in this lesson

Trie: A prefix tree: strings stored as paths of characters from a shared root.
Prefix: The first few characters of a string: "ca" is a prefix of "cart".

Command Palette

Building a Trie

1.Shared prefixes

2.Searching "cart" step by step