28.01Intermediate / Advanced7 topics15 min6 interactive animations

Trie fundamentals

A trie stores strings letter by letter along the edges of a tree, so shared prefixes are stored once and prefix questions take time proportional to the query, not to the number of words.

Learning goals

Describe how a trie represents a set of words with one edge per letter
Map letters to child slots and explain what the word-end flag is for
Implement insert, search and startsWith in O(length of the word)
Delete a word and prune the nodes that no longer serve any word

Prerequisites

Tree fundamentals and traversalStringsArrays

A phone's contact list narrows as you type: after 'ma' it shows only names that start with 'ma'. A trie is the structure behind that behaviour: typing a letter means following one edge, and everything below is a candidate.

28.01.1

Root and edges

A **trie** (also called a prefix tree) is a rooted tree in which every edge carries one letter. The root stands for the empty prefix, and the path from the root to any node spells a prefix. A word is stored as the path that spells it, so words that begin the same way share the beginning of their path.

Try the animation with its default words, car cart cat dog do. The five words need only 8 nodes besides the root, not the 3 + 4 + 3 + 3 + 2 = 15 letters of the words written out: car, cart and cat share the c and a nodes. Looking a word up never compares whole strings; it follows one edge per letter.

Java

1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];          // next[i] is the edge for the letter 'a' + i
4        boolean end;                         // a word ends at this node
5    }
6    private final Node root = new Node();    // the root is the empty prefix
7    boolean isEmpty() {                      // no word has been inserted yet
8        for (Node c : root.next) if (c != null) return false;
9        return !root.end;
10    }
11}

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.

28.01.2

Character mapping

A node needs a way to find the child for a given letter. With a lowercase alphabet the simplest map is c - 'a', which sends 'a' to 0 and 'z' to 25, so a node can keep an array of 26 child references. The subtraction is only valid for the letters the array was sized for: any other character produces a negative or too-large index.

Validate at the boundary. A single check that throws a clear message is much easier to debug than an ArrayIndexOutOfBoundsException deep inside a loop. If the input may contain digits, upper case or Unicode, choose a larger table or a hash map for the children (next lesson).

Character	'a'	'b'	'z'	'A'	'1'
c - 'a'	0	1	25	-32	-48
Valid slot in 26?	yes	yes	yes	no	no

Java

1static int index(char c) {
2    if (c < 'a' || c > 'z') throw new IllegalArgumentException("lowercase letters only: " + c);
3    return c - 'a';
4}
5static char letter(int index) { return (char) ('a' + index); }

28.01.3

Insert

To insert a word, start at the root and, for each letter, follow the child edge if it exists or create it if it does not. After the last letter, mark the node as a word end. Every letter costs one array lookup, so inserting a word of length L takes O(L) time, whatever the number of words already stored.

Watch the 'nodes created' counter in the animation: inserting cart after car creates one node (the t), and cat after both creates one more. A word that is a prefix of an existing word (do after dog) creates no nodes at all and only sets the end flag.

Java

1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5    }
6    private final Node root = new Node();
7    int nodes;                                   // nodes created, besides the root
8    void insert(String word) {
9        Node n = root;
10        for (char c : word.toCharArray()) {
11            int i = c - 'a';
12            if (n.next[i] == null) { n.next[i] = new Node(); nodes++; }   // create the missing edge
13            n = n.next[i];
14        }
15        n.end = true;                            // a word ends here
16    }
17}

Best

O(L)

Average

O(L)

Worst

O(L)

Space

O(L) new nodes at most

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.

28.01.4

Search

To search for a word, follow its letters from the root. If an edge is missing, the word is not stored. If every edge exists, the word is stored only when the last node has its end flag set: reaching a node is not enough, because the path may be a prefix of longer words.

In the animation, choose the query kind contains(word): exact word and the query ca (the preset "Prefix is not a word"): the path exists, but no word ends there, so the answer is false. The preset "Path breaks" shows the other failure, a missing edge at the o of cow.

Java

1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];
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            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    boolean contains(String word) {
17        Node n = root;
18        for (char c : word.toCharArray()) {
19            n = n.next[c - 'a'];
20            if (n == null) return false;         // the path breaks: not stored
21        }
22        return n.end;                            // stored only if a word ends here
23    }
24}

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.

28.01.5

StartsWith

startsWith(prefix) is the question tries answer best. It follows the prefix letter by letter exactly like contains, but it succeeds as soon as the path exists, without looking at the end flag. It runs in O(length of the prefix) however many words there are: a hash set of words cannot do this without scanning every word.

The two queries differ by one condition: contains returns n != null && n.end, startsWith returns n != null. Run the preset "Prefix found": ca is a prefix of car, cart and cat, so the answer is true even though ca is not a word.

Java

1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];
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            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.end = true;
15    }
16    private Node find(String s) {                // the node reached by s, or null
17        Node n = root;
18        for (char c : s.toCharArray()) {
19            n = n.next[c - 'a'];
20            if (n == null) return null;
21        }
22        return n;
23    }
24    boolean startsWith(String prefix) { return find(prefix) != null; }
25}

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.

28.01.6

Word termination

The end flag is what separates a word from a prefix. Without it, the trie would only know which prefixes exist, and ca could not be told apart from car. With it, the same tree stores both: do and dog share a path, and the flag on the o node says that do is a word in its own right.

A boolean is enough for a set of words. To count duplicates (a multiset), replace it by an integer counter: insert increments it, count(word) reads it, and a counter of 0 means 'not a word'. The same counter idea, stored on every node on the path, gives the prefix counts of Lesson 28.03.

Java

1class CountingTrie {
2    private static class Node {
3        Node[] next = new Node[26];
4        int words;                               // how many times a word ends here
5    }
6    private final Node root = new Node();
7    void insert(String word) {
8        Node n = root;
9        for (char c : word.toCharArray()) {
10            int i = c - 'a';
11            if (n.next[i] == null) n.next[i] = new Node();
12            n = n.next[i];
13        }
14        n.words++;
15    }
16    int count(String word) {
17        Node n = root;
18        for (char c : word.toCharArray()) {
19            n = n.next[c - 'a'];
20            if (n == null) return 0;
21        }
22        return n.words;                          // 0 for a mere prefix
23    }
24}

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.

28.01.7

Delete

Deleting has two parts. First unmark the word: clear the end flag at its last node. Then, on the way back up, remove every node that now serves no word, that is, nodes that are not a word end and have no children. Stop at the first node that is still needed. The recursion returns after the deepest node is handled, so the pruning runs naturally from the leaf upwards.

Try the presets. "Prune a leaf chain" deletes cat and removes the t node (7 nodes remain). "Word is a prefix of another" deletes car: the r node still has the child t for cart, so only the flag changes and all 8 nodes stay. "Lazy delete" only unmarks: memory is never returned, but the code is shorter and cannot break other words.

Java

1class Trie {
2    private static class Node {
3        Node[] next = new Node[26];
4        boolean end;
5        int kids;                                // number of non-null children
6    }
7    private final Node root = new Node();
8    void insert(String word) {
9        Node n = root;
10        for (char c : word.toCharArray()) {
11            int i = c - 'a';
12            if (n.next[i] == null) { n.next[i] = new Node(); n.kids++; }
13            n = n.next[i];
14        }
15        n.end = true;
16    }
17    boolean contains(String word) {
18        Node n = root;
19        for (char c : word.toCharArray()) {
20            n = n.next[c - 'a'];
21            if (n == null) return false;
22        }
23        return n.end;
24    }
25    boolean delete(String word) { return delete(root, word, 0); }
26    private boolean delete(Node n, String w, int i) {        // true if the word existed
27        if (i == w.length()) {
28            if (!n.end) return false;            // only a prefix, not a word
29            n.end = false;                       // unmark the word
30            return true;
31        }
32        int c = w.charAt(i) - 'a';
33        Node child = n.next[c];
34        if (child == null || !delete(child, w, i + 1)) return false;
35        if (!child.end && child.kids == 0) {     // the child now serves no word
36            n.next[c] = null;
37            n.kids--;                            // cut it from its parent
38        }
39        return true;
40    }
41}

Trie delete: unmark the word, then prune useless nodes

Interactive · edit the input

trie · 9 nodes

root

word

Being followedRemoved or unmarkedKeptA word ends here

Setup

A trie of 5 words with 8 nodes besides the root. delete("cart") follows the word down, unmarks its last node, and (unless lazy) cuts nodes that no longer serve any word on the way back up.

Step 1 / 10

Java

1boolean delete(String word) { return delete(root, word, 0); }
2private boolean delete(Node n, String w, int i) {        // true if the word existed
3    if (i == w.length()) {
4        if (!n.end) return false;                        // only a prefix, not a word
5        n.end = false;                                   // unmark the word
6        return true;
7    }
8    int c = w.charAt(i) - 'a';
9    Node child = n.next[c];
10    if (child == null || !delete(child, w, i + 1)) return false;   // the path breaks, or no such word
11    if (!child.end && child.kids == 0) {                 // the child now serves no word
12        n.next[c] = null; n.kids--;                      // cut it from its parent
13    }
14    return true;
15}

Live state

8 nodes

words

nodes

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L1	words=5 nodes=8	A trie of 5 words with 8 nodes besides the root. delete("cart") follows the word down, unmarks its last node, and (unless lazy) cuts nodes that no longer serve any word on the way back up.
2	L8	i=1 node="c"	Follow 'c' to the node for "c".
3	L8	i=2 node="ca"	Follow 'a' to the node for "ca".
4	L8	i=3 node="car"	Follow 'r' to the node for "car".
5	L8	i=4 node="cart"	Follow 't' to the node for "cart".
6	L5	end=false kids=0	Unmark the word: end = false. The node has no children and no word ends there any more.
7	L12	child="cart" kids=0 end=false	The node for "cart" has no children and ends no word: cut it from its parent.
8	L12	removed=1 nodes=7	Node removed. Back at "car".
9	L11	child="car" kids=0 end=true	The node for "car" ends another word, so it stays. Everything above it is needed too: stop pruning.
10	L14	return=true removed=1 nodes=7	"cart" deleted; 1 node pruned, 7 remain. The cost is O(length of the word).

Practice ladder

Now try it yourself

Easy

Implement Trie (Prefix Tree)
Longest Word in Dictionary

Medium

Replace Words
Map Sum Pairs

Advanced

Short Encoding of Words
Concatenated Words

Key takeaways

A trie stores one letter per edge, so words that share a beginning share nodes.
contains needs the end flag; startsWith needs only that the path exists. Both cost O(length of the query).
Delete = unmark, then prune nodes that are neither word ends nor parents, from the bottom up.