Implement a Trie (Prefix Tree) with Insert, Search, and startsWith

• Trie (prefix tree) – a tree where each edge represents a character and each root-to-node path spells a prefix.
• Node structure – each node holds child links (map or array) and a boolean isWord marking end of a stored word.
• Insert – walk character by character, create missing children, set isWord on the final node.
• Search – walk character by character; succeed only if every character has a child and the final node has isWord = true.
• startsWith – walk character by character; succeed as long as every character has a child, ignoring isWord.

What is a Trie?

A trie, also called a prefix tree, is a tree data structure where each edge represents a single character and each path from the root spells a prefix. Words that share a prefix share the same initial path through the tree, which is where the space saving comes from.

Each node holds links to its children (one per possible character) and a boolean isWord that marks whether a complete word ends at that node.

How do you implement a TrieNode?

For lowercase English letters, you can use a fixed array of 26 children. For arbitrary characters (like banking reference codes with letters and digits), use a HashMap.

package com.bank.model;

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

public class TrieNode {
    Map<Character, TrieNode> children;
    boolean isWord;

    public TrieNode() {
        this.children = new HashMap<>();
        this.isWord = false;
    }
}

How does insert work?

Insert walks the word character by character from the root. For each character, descend into the matching child, creating it if absent. After consuming the whole word, set isWord = true on the final node.

package com.bank.service;

import com.bank.model.TrieNode;

public class ReferenceCodeTrie {

    private final TrieNode root = new TrieNode();

    public void insert(String code) {
        TrieNode node = root;
        for (char c : code.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isWord = true;
    }

    public boolean search(String code) {
        TrieNode node = findNode(code);
        return node != null && node.isWord;
    }

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

    private TrieNode findNode(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return null;
        }
        return node;
    }

    public static void main(String[] args) {
        ReferenceCodeTrie trie = new ReferenceCodeTrie();
        trie.insert("NBI2024A");
        trie.insert("NBI2024B");
        trie.insert("HDFC001");

        System.out.println("Search NBI2024A: " + trie.search("NBI2024A"));
        System.out.println("Search NBI: " + trie.search("NBI"));
        System.out.println("Prefix NBI: " + trie.startsWith("NBI"));
        System.out.println("Prefix ICICI: " + trie.startsWith("ICICI"));
    }
}

Search NBI2024A: true
Search NBI: false
Prefix NBI: true
Prefix ICICI: false

How is search different from startsWith?

The difference is exactly one line: search checks node.isWord, while startsWith only checks that the path exists.

| Operation | Path must exist | isWord must be true |
|---|---|---|
| search | Yes | Yes |
| startsWith | Yes | No |

// After inserting "NBI2024A":
// search("NBI") returns false -- path exists but isWord is false
// startsWith("NBI") returns true -- path exists, flag irrelevant
// search("NBI2024A") returns true -- path exists AND isWord is true

How is a trie different from a hash set?

| Aspect | Trie | HashSet |
|---|---|---|
| Exact word lookup | O(L) where L = key length | O(L) average (hashing cost) |
| Prefix query | O(L) | O(N) scan all entries |
| Autocomplete | Natural, walk prefix then DFS | Not supported |
| Memory | Higher per-node overhead | Lower for exact lookups |
| Ordered iteration | Lexicographic via DFS | No ordering |

The trie wins when prefix queries matter: autocomplete, typeahead, IP routing tables, and dictionary lookups. A hash set wins for pure exact-match lookups with lower memory.

// HashSet cannot do prefix queries efficiently
Set<String> codeSet = new HashSet<>();
codeSet.add("NBI2024A");
codeSet.add("NBI2024B");
// To find all codes starting with "NBI":
// Must scan every entry: O(N)
for (String code : codeSet) {
    if (code.startsWith("NBI")) { /* ... */ }
}
// Trie: walk to "NBI" node, then DFS: O(prefix length + matches)

What is a compressed trie (radix tree)?

A compressed trie (radix tree) merges chains of single-child nodes into one edge carrying a multi-character label. This reduces memory when many keys share long prefixes.

// Standard trie for "NBIACCOUNT" and "NBILOAN":
// N -> B -> I -> A -> C -> C -> O -> U -> N -> T (10 nodes for path 1)
//                 |-> L -> O -> A -> N          (4 more nodes)

// Radix tree:
// "NBI" -> "ACCOUNT" (2 edges instead of 10+4 nodes)
//       -> "LOAN"

What are the edge cases?

• Empty string – inserting empty string sets root.isWord = true; searching returns true; prefix returns true.
• Search for a word never inserted – returns false at the first missing character.
• Prefix that is also a complete word – both search and startsWith return true.
• Case sensitivity – "NBI" and "nbi" are different keys unless you normalise to one case.

// Edge case: empty string
trie.insert("");
System.out.println(trie.search("")); // true
System.out.println(trie.startsWith("")); // true (every word starts with empty prefix)

What are common mistakes?

The most common mistake is returning true from search when the path exists but isWord is false.

// WRONG: search only checks path existence
public boolean searchBuggy(String code) {
    return findNode(code) != null; // returns true for prefixes too!
}

// CORRECT: check isWord
public boolean search(String code) {
    TrieNode node = findNode(code);
    return node != null && node.isWord;
}

What is the time and space complexity?

Insert, search, and startsWith all run in O(L) time where L is the length of the key. Space is O(total characters across all inserted words) in the worst case (no shared prefixes) or much less when prefixes are shared.

For a banking reference code system with 100,000 codes of average length 10, the trie uses at most 1 million nodes, each holding a small map.

What should a senior engineer know?

A senior engineer should know that tries power autocomplete, typeahead search, spell checkers, IP routing (longest prefix match), and dictionary lookups. The trade-off is memory: each node carries child pointers, so for large alphabets the per-node overhead is significant.

In production, a radix tree or Patricia trie compresses single-child chains. An array-based trie (using a flat character array indexed by position) can be faster for fixed-alphabet keys. The choice between HashMap children and array children depends on the alphabet size: array is faster for small alphabets (26 lowercase letters), HashMap scales better for large alphabets (Unicode).