Implement Trie (Prefix Tree)

1. Problem & Core Objective

Implement a trie supporting three operations:

void    insert(String word)       // add a word
boolean search(String word)       // is this exact word stored?
boolean startsWith(String prefix) // is any stored word prefixed by this?

insert("apple");
search("apple")      → true
search("app")        → false      ← "app" is a prefix, not a stored word
startsWith("app")    → true
insert("app");
search("app")        → true

Constraints: 1 <= word.length <= 2000 · lowercase English letters only · up to 3 × 10^4 calls

What's actually being tested: whether you can build the data structure and — more importantly — whether you understand why it exists. A HashSet matches a trie on search; it's startsWith that a hash set cannot do efficiently. If you can't articulate that, you've implemented a structure without knowing what it's for.

2. First-Principles Thought Process

What a trie actually is

Each edge carries a character; each path from the root spells a prefix. Words sharing a prefix share the path that spells it.

Note what's not stored: no node holds a whole word. The word is the path.

Why isEnd is mandatory

Insert "apple" and the path a-p-p-l-e exists. Now search("app") walks three edges successfully — but "app" was never inserted.

So reaching a node proves the string is a prefix of something stored. It does not prove the string is a stored word. A boolean flag on each node records "a word ends here", and that flag is the entire difference between search and startsWith:

search(w)      → walk to the node, then return node.isEnd
startsWith(p)  → walk to the node, then return true

Two methods, one traversal, differing only in the last line.

Why a trie rather than a hash set

This is the question to have an answer for:

Hashing reads the entire string to compute a bucket, so a HashSet can answer "is this exact string present?" in O(L) — exactly matching a trie. For exact lookup a trie buys you nothing.

But hashing deliberately destroys structure: "app" and "apple" land in unrelated buckets. So startsWith degenerates to scanning every stored word, O(n · L).

A trie keeps prefixes as shared paths, so startsWith is just a walk — O(L), independent of how many words are stored.

The negative answer is the real prize

Beyond speed, the trie can say "no word continues down this path" in O(1) at every step. That's what makes questions 2 and 3 tractable — and it's something a hash set fundamentally cannot offer.

3. Solution Paths

Approach 1 — A HashSet of words (brute force)

class Trie {
    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) {
        for (String w : words)                       // scan everything
            if (w.startsWith(prefix)) return true;
        return false;
    }
}

• Time insert O(L), search O(L), startsWith O(n · L) · Space O(n · L)

Counter-questions on this approach

⭐ "search is O(L) — same as a trie. So what's actually wrong?"

startsWith. Hashing computes a bucket from the whole string, which deliberately scatters related strings — "app" and "apple" have unrelated hash codes. There's no way to ask a hash set "what's near this key?", so the only option is to test every stored word.

With 3 × 10^4 calls against a dictionary of similar size and words up to 2000 characters, that's on the order of 10^9 character comparisons. The trie answers the same question in at most 2000 steps regardless of dictionary size.

⭐ "Could you store every prefix in the set to make startsWith fast?"

You could — insert "a", "ap", "app", "appl", "apple" for each word — and then startsWith becomes O(L). But insertion becomes O(L²) in time and the set stores O(n · L) strings totalling O(n · L²) characters. For a 2000-character word that's 2000 prefixes averaging 1000 characters — two million characters for one word.

That's precisely what a trie does, except the trie shares the prefixes instead of duplicating them. Same capability, linear space.

"Is it ever the right choice?"

If only insert and search were required, absolutely — a HashSet is one line and has better constants than a trie (no pointer chasing, no 26-element arrays). The moment startsWith appears, it stops being viable.

Approach 2 — Array-backed trie nodes (optimal)

class Trie {
    private static class Node {
        Node[] children = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Node();
            node = node.children[i];
        }
        node.isEnd = true;                  // mark where the word ends
    }

    public boolean search(String word)      { Node n = walk(word);   return n != null && n.isEnd; }
    public boolean startsWith(String prefix){ return walk(prefix) != null; }

    private Node walk(String s) {           // the node at the end of s, or null
        Node node = root;
        for (char c : s.toCharArray()) {
            node = node.children[c - 'a'];
            if (node == null) return null;
        }
        return node;
    }
}

Trace — insert "apple", then the three queries:

• Time O(L) for all three operations · Space O(total characters × 26) references

Counter-questions on this approach

⭐ "Why does search need isEnd but startsWith doesn't?"

Because they ask different questions about the same node. Reaching a node proves the string is a prefix of something stored — that alone answers startsWith. Whether the string is itself a stored word is extra information, and isEnd is where it lives.

Without the flag, search("app") would return true after inserting only "apple", which is wrong. The flag is the one thing distinguishing the two methods.

⭐ "new Node[26] at every node — isn't that wasteful?"

It is, and it's the main criticism. A node with one child still allocates 26 references — 104 or 208 bytes depending on compressed oops — so a sparse trie wastes most of its space. With 3 × 10^4 words of up to 2000 characters, the worst case is tens of millions of nodes.

The alternative is Map<Character, Node>, which allocates only for real children. That's better for sparse data or a large alphabet, at the cost of hashing on every step instead of an array index. For 26 lowercase letters the array is usually faster; for Unicode, the map is the only sane choice.

A third option is a compressed trie (radix tree), which collapses chains of single-child nodes into one node holding a substring. That's what production implementations use.

"Why c - 'a' rather than a map lookup?"

It converts a character directly into an array index in one subtraction — no hashing, no allocation, no collision handling. It relies on the constraint that input is lowercase a–z; anything else would index out of bounds. I'd validate or switch to a map if that constraint weren't guaranteed.

"Why factor out walk?"

Because search and startsWith are the same traversal and differ only in what they do at the end. Sharing it makes that explicit and removes a duplicated loop — which is also where a copy-paste bug would live.

"What's the true space complexity?"

O(N × 26) node references where N is the number of distinct prefixes across all words — bounded by the total character count, but usually far less because prefixes are shared. The saving is real but it's not the reason to choose a trie; the prefix query is.

"Can you delete a word?"

Not with this interface, but it's worth knowing: clear isEnd, then walk back up removing any node that has no children and no isEnd. It needs either parent pointers or a recursive implementation that can prune on the way back. Getting it wrong leaks nodes or deletes a shared prefix another word still needs.

Approach 3 — HashMap-backed nodes

private static class Node {
    Map<Character, Node> children = new HashMap<>();
    boolean isEnd;
}

with node.children.get(c) and computeIfAbsent in place of the array indexing.

• Time O(L) with hashing per character · Space proportional to actual children only

Counter-questions on this approach

⭐ "When would you choose this over the array?"

When the alphabet is large or the trie is sparse. For Unicode you obviously can't allocate an array per node. For 26 lowercase letters with dense branching, the array wins on both speed and memory.

The crossover is roughly when the average branching factor drops well below 26 — a dictionary of long, mostly-unique words is sparse near the leaves, so a hybrid (array near the root, map deeper) is what some production tries do.

"Is the hashing cost significant?"

Character.hashCode is trivial, but you also pay boxing — Character objects rather than a raw index — plus a hash lookup and possible collision walk per step. Versus a single array index, it's meaningfully slower in a tight loop, even though both are O(1).

Comparison

4. Why the Optimal Wins

Against the plain HashSet: it simply cannot do startsWith in better than O(n · L), because hashing destroys the relationship between a string and its prefixes.

Against storing every prefix: that does make startsWith fast, and it's worth seeing why it's the wrong shape — it duplicates each prefix once per word, at O(n · L²) characters. The trie stores each distinct prefix once, as a shared path. Same query capability, linear space.

The framing worth keeping:

A hash set answers "is this exact string present?". A trie answers "is this string a prefix of anything?" — and, crucially, can say no in O(1) at every character.

That negative answer is what the next two questions are built on.

5. Java Prerequisites

The node

private static class Node {
    Node[] children = new Node[26];   // dense: fast, 26 refs per node
    boolean isEnd;                     // "a word ends here"
}

static matters — a non-static inner class holds an implicit reference to the enclosing Trie, which is pure overhead at every node.

Character to index

int i = c - 'a';       // 'a' -> 0 ... 'z' -> 25

Lazy child creation

if (node.children[i] == null) node.children[i] = new Node();
node = node.children[i];

With a map, computeIfAbsent(c, k -> new Node()) does both in one call — see 02 §1.3.

toCharArray() vs charAt(i). toCharArray copies once and iterates fast; charAt avoids the copy. For a 2000-character word either is fine — the copy is O(L), which the loop already is.

6. Interview Communication Guide

Clarifying questions: Lowercase only, or full Unicode (lowercase here — it decides array vs map)? Is delete needed (not in this interface, but worth asking)? Can the same word be inserted twice (harmless — isEnd is idempotent)? Rough dictionary size and word length (it decides whether space matters)?

The pitch

"A trie stores characters on edges, so each path from the root spells a prefix, and words with a common prefix share that path.

Each node needs two things: an array of 26 child pointers, and a boolean isEnd. The flag is essential — reaching a node only proves the string is a prefix of something stored. After inserting "apple", the path for "app" exists, but "app" was never a word. isEnd is what distinguishes them.

That makes search and startsWith the same traversal differing only in the last line: search returns node.isEnd, startsWith returns node != null. So I factor the walk out.

All three operations are O(L) in the word length, independent of how many words are stored.

The thing worth saying is why a trie rather than a HashSet. For search they're identical — hashing also reads the whole string, so both are O(L). The difference is startsWith. Hashing deliberately scatters related strings, so a set has to scan everything: O(n · L). A trie keeps prefixes as shared paths, so it's a walk.

You could make a set fast by inserting every prefix of every word, but that's O(n · L²) characters — a trie stores each distinct prefix once instead of once per word.

The main cost is the 26-element array at every node, which wastes space on a sparse trie. A HashMap per node allocates only real children, and is the only option for a large alphabet — I'd switch if the input weren't restricted to lowercase."

Edge cases to volunteer:

Name the first and the empty-prefix case. The first is what isEnd exists for; the second is the one that silently breaks implementations which assume at least one character is consumed.

7. Follow-Up Questions — Modified Constraints

⭐ "Add a delete(String word) method."

Clear isEnd on the final node, then unwind: remove any node that has no children and no isEnd. A recursive implementation handles this naturally by returning "am I now removable?" up the stack. The trap is deleting a node another word still passes through — deleting "app" must not break "apple", which is exactly why the isEnd-and-no-children condition is both clauses.

⭐ "Return all words with a given prefix, not just whether one exists."

Walk to the prefix node, then DFS the subtree collecting every node with isEnd, appending characters as you descend. O(L + total output characters) — optimal, since you must at least write the output. This is autocomplete, and it's the query tries were invented for.

"Count how many words share a prefix."

Store a count in each node, incremented on every insert that passes through. Then it's O(L) with no subtree walk. Same augmentation idea as the subtree sizes in Kth Smallest in a BST — precompute on write to make the read cheap.

"Support Unicode instead of lowercase letters."

The 26-array is out — you'd need a million-element array per node. Use Map<Character, Node>, and note that characters beyond the Basic Multilingual Plane are surrogate pairs in Java, so a char isn't a full code point. Correct handling iterates code points, not chars.

"The dictionary has 10^6 words and memory is tight."

Compress it. A radix tree collapses single-child chains into one node holding a substring, which dramatically shrinks deep sparse tries. Beyond that, a DAWG (directed acyclic word graph) merges identical suffixes as well as prefixes, and a succinct trie encodes the structure in roughly 2 bits per node. Each trades update flexibility for size.

"Support case-insensitive lookup."

Normalise on the way in and on every query — lowercase both. Storing both cases would double the trie for no benefit. Worth stating that normalisation belongs at the boundary, not scattered through the traversal.