Tries in Java

A trie (also called a prefix tree) stores a set of strings one character per level. Each edge is labeled with a character, and following edges from the root spells a string. Words that share a prefix share the path for that prefix, and each node records whether a word ends there.

Example: the words the, then, there, to, and a:

graph TB
    root(("root")) -->|t| t["t"]
    root -->|a| a["a (end)"]
    t -->|h| th["th"]
    t -->|o| to["to (end)"]
    th -->|e| the["the (end)"]
    the -->|n| then["then (end)"]
    the -->|r| ther["ther"]
    ther -->|e| there["there (end)"]

"the", "then", and "there" share the nodes for t, h, e. The node for th exists, but no word ends there, so th is a prefix but not a word.

Costs

For a word of length L:

Operation	Trie	`HashSet<String>`
insert	`O(L)`	`O(L)` to hash
is this a word?	`O(L)`	`O(L)` to hash
does any word start with this prefix?	`O(L)`	`O(total length of all words)`: scan everything
list every word with a prefix, in sorted order	`O(L + size of the output)`	scan and sort

The trie's advantage is prefix questions. For plain "is this a word?" lookups, a HashSet is simpler and uses less memory.

The node type

For lowercase English letters, each node has 26 child slots, one per letter, and a flag that marks the end of a word:

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26]; // children[0] is 'a', children[25] is 'z'
        boolean isEnd;
    }

    public static void main(String[] args) {
        TrieNode node = new TrieNode();
        System.out.println(node.children.length + " " + node.children[2] + " " + node.isEnd);
    }
}

Output

26 null false

A new array of object references starts with every slot null, so a new TrieNode is an empty node. null in a slot means "no child for this letter". Fields are mutable references, so no Box or Option wrapper is needed.

A letter's slot is its offset from 'a': c - 'a', where c is the char. 'c' is 99 and 'a' is 97, so 'c' goes in slot 2. A char is a 16-bit code unit, and subtracting two char values gives an int.

Insert, search, and prefix lookup

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    static class Trie {
        TrieNode root = new TrieNode();

        void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                int slot = word.charAt(i) - 'a';
                if (node.children[slot] == null) {
                    node.children[slot] = new TrieNode(); // create the child if it is missing
                }
                node = node.children[slot];
            }
            node.isEnd = true;
        }

        /** The node reached by following prefix, or null if that path does not exist. */
        TrieNode find(String prefix) {
            TrieNode node = root;
            for (int i = 0; i < prefix.length(); i++) {
                node = node.children[prefix.charAt(i) - 'a'];
                if (node == null) return null;
            }
            return node;
        }

        boolean search(String word) {
            TrieNode node = find(word);
            return node != null && node.isEnd;
        }

        boolean startsWith(String prefix) {
            return find(prefix) != null;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        for (String w : new String[] {"the", "then", "there", "to", "a"}) {
            trie.insert(w);
        }
        System.out.println("search:      the=" + trie.search("the") + " th=" + trie.search("th") + " tea=" + trie.search("tea"));
        System.out.println("startsWith:   th=" + trie.startsWith("th") + " tx=" + trie.startsWith("tx"));
    }
}

Output

search:      the=true th=false tea=false
startsWith:   th=true tx=false

How the pieces work:

insert follows the existing child in each slot, or creates an empty node there first. Then node moves down to it.
find returns null as soon as a character has no child. Returning null means "no such path".
search needs the path to exist and end on a node with isEnd set. startsWith only needs the path to exist.

Walkthrough of search("th"): root → child t exists → child h exists → end of input. The node for th has isEnd == false, so the result is false. startsWith("th") returns true for the same path.

Delete and prune

To delete a word, clear its end flag. Then, on the way back up, remove any node that no longer leads to a word: it has no end flag and no children. Recursion makes this easy, because each call can report back to its parent whether the child should be removed.

Java

public class Main {
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    static void insert(TrieNode root, String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int slot = word.charAt(i) - 'a';
            if (node.children[slot] == null) node.children[slot] = new TrieNode();
            node = node.children[slot];
        }
        node.isEnd = true;
    }

    static boolean hasNoChildren(TrieNode node) {
        for (TrieNode child : node.children) {
            if (child != null) return false;
        }
        return true;
    }

    /** Returns true if the word was present and has been removed. */
    static boolean remove(TrieNode node, String word, int depth) {
        if (depth == word.length()) {
            // End of the word: clear the flag and report whether it was set.
            boolean wasEnd = node.isEnd;
            node.isEnd = false;
            return wasEnd;
        }
        int slot = word.charAt(depth) - 'a';
        TrieNode child = node.children[slot];
        if (child == null) return false; // the word isn't in the trie
        boolean removed = remove(child, word, depth + 1);
        if (removed && !child.isEnd && hasNoChildren(child)) {
            node.children[slot] = null; // the child leads to no word anymore
        }
        return removed;
    }

    static int countNodes(TrieNode node) {
        int total = 1;
        for (TrieNode child : node.children) {
            if (child != null) total += countNodes(child);
        }
        return total;
    }

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        insert(root, "the");
        insert(root, "then");
        System.out.println("nodes: " + countNodes(root)); // root + t, h, e, n
        boolean removed = remove(root, "then", 0);
        System.out.println("removed then: " + removed + ", nodes: " + countNodes(root));
        System.out.println("removed then again: " + remove(root, "then", 0));
        System.out.println("removed th: " + remove(root, "th", 0)); // a prefix, not a word
    }
}

Output

nodes: 5
removed then: true, nodes: 4
removed then again: false
removed th: false

Removing then deletes only the n node. the still needs the path t → h → e, and the node for e still has isEnd set, so the pruning stops there. Setting a slot to null drops the only reference to the removed node, and the garbage collector reclaims it.

Other alphabets: a `HashMap` of children

The 26-slot array is fast, but it only covers a to z, and every node uses 26 slots even when it has one child. For arbitrary characters, or to save memory, store the children in a HashMap<Character, TrieNode>. The map's keys are boxed Character objects, and computeIfAbsent creates the child when the key is missing.

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEnd;

        void insert(String word) {
            TrieNode node = this;
            for (int i = 0; i < word.length(); i++) {
                node = node.children.computeIfAbsent(word.charAt(i), c -> new TrieNode());
            }
            node.isEnd = true;
        }

        boolean search(String word) {
            TrieNode node = this;
            for (int i = 0; i < word.length(); i++) {
                node = node.children.get(word.charAt(i));
                if (node == null) return false;
            }
            return node.isEnd;
        }
    }

    public static void main(String[] args) {
        TrieNode root = new TrieNode();
        for (String w : new String[] {"café", "cafe", "日本"}) {
            root.insert(w);
        }
        System.out.println(root.search("café") + " " + root.search("caf") + " " + root.search("日本"));
    }
}

Output

true false true

A Java char is a 16-bit UTF-16 code unit. This works for the characters above because each fits in one char. A character outside the Basic Multilingual Plane, such as most emoji, takes two char values, and a trie over char would store it as two separate edges. To treat each character as one edge, iterate with word.codePoints() and key the map by Integer.

With a HashMap, the children are not kept in alphabetical order, and their iteration order is unspecified. Problems that need sorted output (such as listing all words in order) should use a TreeMap<Character, TrieNode> instead.

When to use a trie

Prefix queries: autocomplete, "does any word start with ...?", counting words with a prefix.
Many lookups against one dictionary while walking a string: splitting a string into dictionary words, or searching a letter grid for words. A trie lets you stop as soon as the current prefix matches no word.
Sorted output: a depth-first walk that visits children from a to z lists the words in lexicographic order.

The following lessons use the 26-slot trie from this page.

Interview points

Insert, search, and prefix lookup each cost O(L) for a word of length L, independent of how many words the trie holds.
A prefix query on a HashSet<String> scans every word; a trie answers it in O(L).
search needs isEnd on the final node; startsWith only needs the path.
Deletion clears isEnd and prunes nodes with no children and no end flag on the way back up.
The 26-slot array uses 26 references per node; a HashMap or TreeMap of children saves memory and supports other alphabets.
A depth-first walk from a to z lists words in lexicographic order.

Summary

A trie stores one character per edge; words with a shared prefix share a path.
Each node has child references (null when absent) and an isEnd flag.
A char slot is c - 'a' for lowercase letters.
Prefix questions are the reason to choose a trie over a hash set.
Java uses mutable node references and null, so no wrapper types are needed.

Costs

The node type

Insert, search, and prefix lookup

Delete and prune

Other alphabets: a HashMap of children

When to use a trie

Interview points

Summary

Other alphabets: a `HashMap` of children