DSA-089 · FOCUSED PRACTICE

Implement Trie — Insert, Search, Prefix

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 15491 deterministic checks. Learner drafts are not executed.

Understand the problem

Implement a Trie supporting insert(word), search(word), and startsWith(prefix). Search tests whether a complete inserted word exists; startsWith tests whether a prefix path exists.

Each argument is a non-null string of 0–1,000 lowercase English letters a–z. Up to 10,000 operations are supported; other alphabets and null are outside the contract.
Inserting a word twice is idempotent. Empty word is valid: search("") becomes true only after inserting it. startsWith("") is always true, including an empty Trie, because the root path exists.
Each Trie instance owns independent mutable state. Query operations do not create nodes or change terminal markers. There is no delete or frequency operation.

Examples

Input: insert("apple"); search("apple"); search("app"); startsWith("app")
Output: true, false, true
The app path exists, but it is not a complete word until inserted.
Input: search(""); startsWith(""); insert(""); search("")
Output: false, true, true
The root exists initially; its terminal flag is initially false.

Before you start

Character-indexed child references
A complete word versus an existing prefix path

Recognize the structure

Many words share leading paths. A trie spends work by queried length rather than scanning every stored word for prefixes. A hash set is already strong for exact-word membership but does not directly answer general prefix queries.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 141/20,000 characters

Self-review

I distinguish paths from terminal words.I define alphabet and empty-string behavior.My queries cannot mutate shared state.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Words with a common prefix can share work.

Hint 2

What marks that a word ends before its path does?

Hint 3

Store child edges and a terminal flag; insert allocates, queries only walk.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Store complete words in a set

Insertion and exact search use a HashSet<String>; a prefix query scans stored words with startsWith. If only "apple" is stored, exact "app" is false but a prefix scan finds it. The empty prefix is handled explicitly as true even before any word exists. For W words and prefix length L, a worst-case prefix scan costs O(WL); Java string hashing/equality also examines content, so exact lookup is not free in L.

Improve the baseline

Share prefixes as nodes

Use one root and 26 child slots per node. Each character follows one edge, allocating missing nodes only during insert.

Separate path existence from a whole word

At the final insertion node, set terminal=true. A search succeeds only if walk reaches a node whose terminal flag is set.

Let queries only walk

walk returns null on a missing edge and never creates it. startsWith accepts any reached node; empty input walks zero edges and reaches root.

Why it is correct

Initialize

Only root exists, with terminal=false. It represents the empty path but not an inserted empty word.

Preserve insertion meaning

After processing i characters, node represents exactly the length-i prefix. Following or creating the next edge establishes the next prefix. Marking only the final node terminal records exactly the inserted word; existing paths and terminal words remain valid.

Establish query results

A missing edge proves no inserted word created that prefix path. A complete walk proves a prefix exists, but only its terminal marker proves a whole word was inserted. Finite input length bounds every walk.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.HashSet;
import java.util.Set;

public final class Solution {
    public static final class Trie {
        private static final class Node {
            final Node[] children = new Node[26];
            boolean terminal;
        }
        private final Node root = new Node();

        public void insert(String word) {
            Node node = root;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (node.children[index] == null) node.children[index] = new Node();
                node = node.children[index];
            }
            node.terminal = true;
        }
        private Node walk(String text) {
            Node node = root;
            for (int i = 0; i < text.length(); i++) {
                node = node.children[text.charAt(i) - 'a'];
                if (node == null) return null;
            }
            return node;
        }
        public boolean search(String word) {
            Node node = walk(word);
            return node != null && node.terminal;
        }
        public boolean startsWith(String prefix) { return walk(prefix) != null; }
    }

    public static final class Baseline {
        private final Set<String> words = new HashSet<>();
        public void insert(String word) { words.add(word); }
        public boolean search(String word) { return words.contains(word); }
        public boolean startsWith(String prefix) {
            if (prefix.isEmpty()) return true;
            for (String word : words) if (word.startsWith(prefix)) return true;
            return false;
        }
    }
}

Read the meaningful blocks

Own the root per instance

A static root would leak words between unrelated Trie instances.

Use char-a under an explicit alphabet

The fixed array is safe only because the contract excludes other characters.

Keep terminal separate

A path may be shared by several longer words without being an inserted word itself.

Complexity

Insert, search, and startsWith take O(L) character transitions, plus constant work for L=0. Allocating a new node initializes 26 child slots, a fixed constant under this alphabet.

If P distinct nonempty prefix nodes are created, the trie occupies O(26(P+1)) references plus flags, i.e. O(P+1) for fixed alphabet. Query workspace is O(1). The set baseline stores complete strings/references and scans up to W strings for a prefix query.

Exact-state walkthroughs

Reveal normal and boundary traces

Prefix versus complete word

Input: {"operations":[["insert","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]} · Result: [null,false,true,null,true]

Step 1 of 24: Root path exists without a terminal word.

The empty prefix exists initially; the empty word does not.

Existing trie paths and terminal words

(root)prefix path only

A terminal marker and path existence are different. These cards summarize exact paths, rather than array indices.

State after this step
Variable	Value
paths	`[""]`
terminalWords	`[]`
outputs	`[]`

See the affected Java block

 1 import java.util.HashSet;
 2 import java.util.Set;
 3 
 4 public final class Solution {
 5     public static final class Trie {
 6         private static final class Node {
 7             final Node[] children = new Node[26];
 8             boolean terminal;
 9         }
10         private final Node root = new Node();
11 
12         public void insert(String word) {
13             Node node = root;
14             for (int i = 0; i < word.length(); i++) {
15                 int index = word.charAt(i) - 'a';
16                 if (node.children[index] == null) node.children[index] = new Node();
17                 node = node.children[index];
18             }
19             node.terminal = true;
20         }
21         private Node walk(String text) {
22             Node node = root;
23             for (int i = 0; i < text.length(); i++) {
24                 node = node.children[text.charAt(i) - 'a'];
25                 if (node == null) return null;
26             }
27             return node;
28         }
29         public boolean search(String word) {
30             Node node = walk(word);
31             return node != null && node.terminal;
32         }
33         public boolean startsWith(String prefix) { return walk(prefix) != null; }
34     }
35 
36     public static final class Baseline {
37         private final Set<String> words = new HashSet<>();
38         public void insert(String word) { words.add(word); }
39         public boolean search(String word) { return words.contains(word); }
40         public boolean startsWith(String prefix) {
41             if (prefix.isEmpty()) return true;
42             for (String word : words) if (word.startsWith(prefix)) return true;
43             return false;
44         }
45     }
46 }
47

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Root path exists without a terminal word.
The empty prefix exists initially; the empty word does not.
paths
[""]
terminalWords
[]
outputs
[]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"apple"
cursor
"a"
paths
["","a"]
terminalWords
[]
outputs
[]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"apple"
cursor
"ap"
paths
["","a","ap"]
terminalWords
[]
outputs
[]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"apple"
cursor
"app"
paths
["","a","ap","app"]
terminalWords
[]
outputs
[]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"apple"
cursor
"appl"
paths
["","a","ap","app","appl"]
terminalWords
[]
outputs
[]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"apple"
cursor
"apple"
paths
["","a","ap","app","appl","apple"]
terminalWords
[]
outputs
[]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"insert"
text
"apple"
cursor
"apple"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"a"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"ap"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"search"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false]
Follow one character edge.
cursor names the exact represented prefix.
operation
"startsWith"
text
"app"
cursor
"a"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false]
Follow one character edge.
cursor names the exact represented prefix.
operation
"startsWith"
text
"app"
cursor
"ap"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false]
Follow one character edge.
cursor names the exact represented prefix.
operation
"startsWith"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"startsWith"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false,true]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"app"
cursor
"a"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false,true]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"app"
cursor
"ap"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false,true]
Follow one character edge.
cursor names the exact represented prefix.
operation
"insert"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple"]
outputs
[null,false,true]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"insert"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple","app"]
outputs
[null,false,true,null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"a"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple","app"]
outputs
[null,false,true,null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"ap"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple","app"]
outputs
[null,false,true,null]
Follow one character edge.
cursor names the exact represented prefix.
operation
"search"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple","app"]
outputs
[null,false,true,null]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"search"
text
"app"
cursor
"app"
paths
["","a","ap","app","appl","apple"]
terminalWords
["apple","app"]
outputs
[null,false,true,null,true]
Return the contract result.
The final state satisfies the requested output contract.
result
[null,false,true,null,true]

Empty path and root terminal

Input: {"operations":[["search",""],["startsWith",""],["insert",""],["search",""]]} · Result: [false,true,null,true]

Step 1 of 6: Root path exists without a terminal word.

The empty prefix exists initially; the empty word does not.

Existing trie paths and terminal words

(root)prefix path only

A terminal marker and path existence are different. These cards summarize exact paths, rather than array indices.

State after this step
Variable	Value
paths	`[""]`
terminalWords	`[]`
outputs	`[]`

See the affected Java block

 1 import java.util.HashSet;
 2 import java.util.Set;
 3 
 4 public final class Solution {
 5     public static final class Trie {
 6         private static final class Node {
 7             final Node[] children = new Node[26];
 8             boolean terminal;
 9         }
10         private final Node root = new Node();
11 
12         public void insert(String word) {
13             Node node = root;
14             for (int i = 0; i < word.length(); i++) {
15                 int index = word.charAt(i) - 'a';
16                 if (node.children[index] == null) node.children[index] = new Node();
17                 node = node.children[index];
18             }
19             node.terminal = true;
20         }
21         private Node walk(String text) {
22             Node node = root;
23             for (int i = 0; i < text.length(); i++) {
24                 node = node.children[text.charAt(i) - 'a'];
25                 if (node == null) return null;
26             }
27             return node;
28         }
29         public boolean search(String word) {
30             Node node = walk(word);
31             return node != null && node.terminal;
32         }
33         public boolean startsWith(String prefix) { return walk(prefix) != null; }
34     }
35 
36     public static final class Baseline {
37         private final Set<String> words = new HashSet<>();
38         public void insert(String word) { words.add(word); }
39         public boolean search(String word) { return words.contains(word); }
40         public boolean startsWith(String prefix) {
41             if (prefix.isEmpty()) return true;
42             for (String word : words) if (word.startsWith(prefix)) return true;
43             return false;
44         }
45     }
46 }
47

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Root path exists without a terminal word.
The empty prefix exists initially; the empty word does not.
paths
[""]
terminalWords
[]
outputs
[]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"search"
text
""
cursor
""
paths
[""]
terminalWords
[]
outputs
[false]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"startsWith"
text
""
cursor
""
paths
[""]
terminalWords
[]
outputs
[false,true]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"insert"
text
""
cursor
""
paths
[""]
terminalWords
[""]
outputs
[false,true,null]
Finish the operation.
Terminal membership, not path existence alone, answers exact search.
operation
"search"
text
""
cursor
""
paths
[""]
terminalWords
[""]
outputs
[false,true,null,true]
Return the contract result.
The final state satisfies the requested output contract.
result
[false,true,null,true]

Test the contract

Input: new Trie; search("a")
Output: false
Missing edge.
Input: insert("a"); search("aa")
Output: false
Longer missing suffix.
Input: insert("app"); insert("apple"); search("app")
Output: true
Short word remains terminal.
Input: two separate Tries; insert("a") in first; search("a") in second
Output: false
Instance isolation.

Common mistakes and counterexamples

Treat every path as a word

Counterexample: After insert("apple"), search("app") must be false.

Require terminal at the last node.

Create nodes during search

Counterexample: Searching a missing prefix could make startsWith incorrectly succeed later.

Queries only walk existing edges.

Forget empty semantics

Counterexample: startsWith("") is true before insertion, but search("") is false.

Root path and root terminal are separate facts.

Follow-ups

Add delete(word).

Clear its terminal marker and prune only childless nonterminal nodes. Shared prefixes must survive; duplicate insertion semantics must be fixed before adding counts.

Support wildcard search.

A wildcard branches over existing children. Complexity depends on the number of explored trie nodes, not merely the word length; exact-prefix walking no longer suffices.

Support arbitrary Unicode code points.

Replace 26 slots by a map keyed by code point and state normalization rules. Cost becomes expected map lookup per edge; memory and grapheme semantics change.

Related foundations

Tries: a path is not automatically a word

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.