28.02Intermediate / Advanced5 topics14 min1 interactive animation

Trie implementation

How to build a trie in Java: array or hash-map children, what a node costs in memory, how to shrink the alphabet, and when to prefer a loop over recursion.

Learning goals

Choose between an array and a HashMap for the children of a node
Estimate the memory a node costs and why tries can be memory hungry
Shrink child storage with a bitmask when most nodes have few children
Write both an iterative and a recursive walk and pick the right one

Prerequisites

Trie fundamentalsHash tablesBit manipulation

A trie trades memory for speed. The same idea can be coded as a compact 26-slot array or as a flexible map; knowing the price of each decides whether the structure fits in memory at all.

28.02.1

Array child pointers

The array layout gives every node a Node[] of the alphabet size. The child for a letter is one array read, with no hashing and no boxing, so it is the fastest layout when the alphabet is small and fixed. Choosing the alphabet size as a constructor parameter makes the same class work for digits (10), DNA (4) or lowercase letters (26).

The price is space: every node pays for all its slots even if it has one child. A node of a word list with long, unshared tails (for example a dictionary of 10-letter names) is mostly empty slots.

Java

1class ArrayTrie {
2    private static class Node {
3        final Node[] next;
4        boolean end;
5        Node(int sigma) { next = new Node[sigma]; }
6    }
7    private final int sigma;
8    private final char first;                    // the letter that maps to slot 0
9    private final Node root;
10    int nodes;
11    ArrayTrie(int sigma, char first) { this.sigma = sigma; this.first = first; this.root = new Node(sigma); }
12    void insert(String word) {
13        Node n = root;
14        for (char c : word.toCharArray()) {
15            int i = c - first;
16            if (i < 0 || i >= sigma) throw new IllegalArgumentException("outside the alphabet: " + c);
17            if (n.next[i] == null) { n.next[i] = new Node(sigma); nodes++; }
18            n = n.next[i];
19        }
20        n.end = true;
21    }
22    boolean contains(String word) {
23        Node n = root;
24        for (char c : word.toCharArray()) {
25            int i = c - first;
26            if (i < 0 || i >= sigma || (n = n.next[i]) == null) return false;
27        }
28        return n.end;
29    }
30}

28.02.2

HashMap child map

A HashMap<Character, Node> per node stores only the children that exist. It handles any alphabet, including digits, upper case, punctuation and any UTF-16 code unit, without choosing a size in advance. Nodes with one child cost one map entry instead of 26 slots.

The price is time and per-entry overhead: each lookup hashes a boxed Character, and a HashMap has a table and entry objects of its own, so for dense nodes it is larger than an array. A common compromise is to create the map lazily, so leaves (which have no children) do not allocate one.

Java

1class MapTrie {
2    private static class Node {
3        Map<Character, Node> next;               // created on first use: leaves have none
4        boolean end;
5    }
6    private final Node root = new Node();
7    void insert(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            if (n.next == null) n.next = new HashMap<>();
11            n = n.next.computeIfAbsent(c, k -> new Node());
12        }
13        n.end = true;
14    }
15    boolean contains(String word) {
16        Node n = root;
17        for (char c : word.toCharArray()) {
18            if (n.next == null || (n = n.next.get(c)) == null) return false;
19        }
20        return n.end;
21    }
22    boolean startsWith(String prefix) {
23        Node n = root;
24        for (char c : prefix.toCharArray()) {
25            if (n.next == null || (n = n.next.get(c)) == null) return false;
26        }
27        return true;
28    }
29}

28.02.3

Node memory

Tries can use much more memory than the strings they hold, so it is worth estimating. On a typical 64-bit HotSpot JVM with compressed references, a Node object with a reference to its child array and a boolean takes about 24 bytes (12-byte header, 4-byte reference, 1 byte, padded to a multiple of 8), and a Node[26] array takes 16 + 26 × 4 = 120 bytes. That is about 144 bytes per node, even for a leaf with no children.

The numbers below are layout estimates, not measurements: the exact sizes depend on the JVM and its flags, and the JOL tool or a heap dump gives the real figures for your machine. The shape of the argument does not change: with the array layout every node pays for the whole alphabet, so the cost grows with the number of nodes times the alphabet size, not with the number of words.

Child storage	Per-node cost (estimate)	Lookup	Best for
Node[26] array	about 144 bytes	one array read	small, fixed alphabet; dense nodes
HashMap per node	a map object, its table and one entry object per child	hash + compare	large or unknown alphabet; sparse nodes
Bitmask + compact array	the node, one int and an array with one reference per existing child	bitCount + array read	many sparse nodes with a small alphabet

Java

1static long align(long bytes) { return (bytes + 7) / 8 * 8; }          // objects are padded to 8 bytes
2// estimate for a 64-bit HotSpot JVM with compressed references
3static long arrayNodeBytes(int alphabet) {
4    long node = align(12 + 4 + 1);               // header, array reference, boolean
5    long slots = align(16 + 4L * alphabet);      // array header (with length) + one reference per slot
6    return node + slots;
7}

28.02.4

Compressed alphabets

A middle path keeps the speed of array indexing while paying only for children that exist. Each node stores a bitmask with one bit per letter and a compact array holding just the present children. The slot of letter c is the number of set bits below bit c, which Integer.bitCount computes in one instruction.

Lookups stay O(1) per letter. The cost moves to insertion: adding a child in the middle means growing and shifting the compact array. This layout suits tries that are built once and queried many times, such as a dictionary loaded at start-up.

Java

1class BitTrie {
2    private static class Node {
3        int mask;                                // bit i set: the child for letter 'a' + i exists
4        Node[] kids = new Node[0];               // only the children that exist, in letter order
5        boolean end;
6    }
7    private final Node root = new Node();
8    private static int slot(Node n, int i) { return Integer.bitCount(n.mask & ((1 << i) - 1)); }
9    void insert(String word) {
10        Node n = root;
11        for (char c : word.toCharArray()) {
12            int i = c - 'a';
13            int s = slot(n, i);
14            if ((n.mask & (1 << i)) == 0) {      // add a child: grow the array and open slot s
15                Node[] bigger = new Node[n.kids.length + 1];
16                System.arraycopy(n.kids, 0, bigger, 0, s);
17                bigger[s] = new Node();
18                System.arraycopy(n.kids, s, bigger, s + 1, n.kids.length - s);
19                n.kids = bigger;
20                n.mask |= 1 << i;
21            }
22            n = n.kids[s];
23        }
24        n.end = true;
25    }
26    boolean contains(String word) {
27        Node n = root;
28        for (char c : word.toCharArray()) {
29            int i = c - 'a';
30            if ((n.mask & (1 << i)) == 0) return false;
31            n = n.kids[slot(n, i)];
32        }
33        return n.end;
34    }
35}

28.02.5

Iterative vs recursive walk

Insertion, search and prefix queries walk one path, so a loop is the natural form: no stack frames, no recursion limit, and the code is shorter. Use recursion when the walk must come back, as when pruning during delete or exploring all branches for wildcards and autocomplete (Lesson 28.03 and 28.04).

A recursive walk uses stack space proportional to the word length. For words of a few dozen letters that is harmless; for very long keys (thousands of characters) the loop avoids a possible StackOverflowError. Both versions below behave identically on every input.

Java

1class WalkTrie {
2    private static class Node { Node[] next = new Node[26]; boolean end; }
3    private final Node root = new Node();
4    void insert(String word) {                   // iterative: one loop, no stack
5        Node n = root;
6        for (char c : word.toCharArray()) {
7            int i = c - 'a';
8            if (n.next[i] == null) n.next[i] = new Node();
9            n = n.next[i];
10        }
11        n.end = true;
12    }
13    boolean containsIterative(String word) {
14        Node n = root;
15        for (char c : word.toCharArray()) {
16            n = n.next[c - 'a'];
17            if (n == null) return false;
18        }
19        return n.end;
20    }
21    boolean containsRecursive(String word) { return contains(root, word, 0); }
22    private boolean contains(Node n, String w, int i) {      // recursive: one frame per letter
23        if (n == null) return false;
24        if (i == w.length()) return n.end;
25        return contains(n.next[w.charAt(i) - 'a'], w, i + 1);
26    }
27}

Trie: insert words, then search a word or a prefix

Interactive · edit the input

trie · 1 node

root

Being followedNew nodeMatchMissing edgeA word ends here

Setup

An empty trie: only the root. Each edge is one letter; a word is the path from the root to a node marked as an ending.

Step 1 / 25

Java

1class Trie {
2    private static class Node { Node[] next = new Node[26]; boolean end; }
3    private final Node root = new Node();
4    void insert(String word) {
5        Node n = root;
6        for (char c : word.toCharArray()) {
7            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();    // create the missing edge
8            n = n.next[c - 'a'];
9        }
10        n.end = true;                                                      // a word ends here
11    }
12    private Node find(String s) {
13        Node n = root;
14        for (char c : s.toCharArray()) {
15            n = n.next[c - 'a'];
16            if (n == null) return null;                                    // the path breaks
17        }
18        return n;
19    }
20    boolean contains(String word) { Node n = find(word); return n != null && n.end; }
21    boolean startsWith(String prefix) { return find(prefix) != null; }
22}

Live state

0 nodes created

words

No condition evaluated on this step

Execution trace (dry run table)Show 25 steps

Step	Line	State	What happens
1	L3	words=5	An empty trie: only the root. Each edge is one letter; a word is the path from the root to a node marked as an ending.
2	L7	word=car char=c nodes created=1	insert("car"): there is no 'c' edge below "root", so a new node is created.
3	L7	word=car char=a nodes created=2	insert("car"): there is no 'a' edge below "c", so a new node is created.
4	L7	word=car char=r nodes created=3	insert("car"): there is no 'r' edge below "ca", so a new node is created.
5	L10	word=car new nodes=3	Mark the last node of "car" as a word ending (3 new nodes).
6	L8	word=cart char=c	insert("cart"): the 'c' edge already exists (a shared prefix), so it is reused: no new node.
7	L8	word=cart char=a	insert("cart"): the 'a' edge already exists (a shared prefix), so it is reused: no new node.
8	L8	word=cart char=r	insert("cart"): the 'r' edge already exists (a shared prefix), so it is reused: no new node.
9	L7	word=cart char=t nodes created=4	insert("cart"): there is no 't' edge below "car", so a new node is created.
10	L10	word=cart new nodes=1	Mark the last node of "cart" as a word ending (1 new node).
11	L8	word=cat char=c	insert("cat"): the 'c' edge already exists (a shared prefix), so it is reused: no new node.
12	L8	word=cat char=a	insert("cat"): the 'a' edge already exists (a shared prefix), so it is reused: no new node.
13	L7	word=cat char=t nodes created=5	insert("cat"): there is no 't' edge below "ca", so a new node is created.
14	L10	word=cat new nodes=1	Mark the last node of "cat" as a word ending (1 new node).
15	L7	word=dog char=d nodes created=6	insert("dog"): there is no 'd' edge below "root", so a new node is created.
16	L7	word=dog char=o nodes created=7	insert("dog"): there is no 'o' edge below "d", so a new node is created.
17	L7	word=dog char=g nodes created=8	insert("dog"): there is no 'g' edge below "do", so a new node is created.
18	L10	word=dog new nodes=3	Mark the last node of "dog" as a word ending (3 new nodes).
19	L8	word=do char=d	insert("do"): the 'd' edge already exists (a shared prefix), so it is reused: no new node.
20	L8	word=do char=o	insert("do"): the 'o' edge already exists (a shared prefix), so it is reused: no new node.
21	L10	word=do new nodes=0	Mark the last node of "do" as a word ending (no new nodes were needed: it was a prefix of existing words).
22	L13	query=ca	startsWith("ca"): follow the query letter by letter from the root.
23	L15	query=ca char=c matched=1	'c' edge exists: now at the node for "c".
24	L15	query=ca char=a matched=2	'a' edge exists: now at the node for "ca".
25	L21	return=true	The whole prefix was found: startsWith("ca") = true. Cost: O(2), independent of how many words are stored.

Practice ladder

Now try it yourself

Easy

Implement Trie (Prefix Tree)
Longest Common Prefix

Medium

Implement Trie II (Prefix Tree)
Design Add and Search Words Data Structure

Advanced

Stream of Characters
Palindrome Pairs

Key takeaways

Array children are fastest but pay for the whole alphabet in every node; maps pay per child but cost more per lookup.
Estimate memory as nodes × per-node cost, not words × length, and measure it on your own JVM.
Use a loop for single-path walks and recursion when the walk must return, such as pruning and enumeration.