Basic Trie

Insert & Search

Insert: for each character, if the child doesn't exist, create it. Move to the child. Mark the last node as 'end of word'. Search: walk the same path. If any child is missing, the word doesn't exist. Check the end marker.

O(m) per word

O(n*m)

say this out loud

Prefix queries are what a hash map cannot do, so a trie. Each node holds children plus an end-of-word flag, and lookup is O(L) in the word length.

How It Works

A trie node holds an array or map of children keyed by character, plus a boolean end-of-word flag. Insertion walks from the root one character at a time, creating any child that does not yet exist, and marks the final node as a word terminator. Search walks the identical path; if a required child is missing the word is absent, and if the walk completes, the end flag decides between a stored word and a mere prefix of one.

Both operations cost O(L) for a word of length L, independent of how many words the trie holds, a hash map matches that lookup bound but cannot share prefixes or support ordered prefix traversal. Space is the trade-off: each node may reserve 26 child slots, so memory is O(total characters * alphabet) in the array form, which the map-based form reduces at some speed cost.

Step-by-Step Visualization

Insert "apple" into a trie

nodesjust the root

1/9

Code

Java

class TrieNode {
  Map<Character, TrieNode> children = new HashMap<>();
  boolean isEnd = false;
}

class Trie {
  TrieNode root = new TrieNode();

  void insert(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
      node.children.putIfAbsent(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  boolean search(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
      if (!node.children.containsKey(ch)) return false;
      node = node.children.get(ch);
    }
    return node.isEnd;
  }
}

Tips & Gotchas

1Each node has children map (char → node) and isEnd flag

2Insert: create nodes as needed for each character

3Search: follow existing nodes; fail if any char missing

Practice Problems

1Implement Trie (Prefix Tree)
2Design Add and Search Words Data Structure
3Longest Word in Dictionary

About the Basic Trie Pattern

Each node has up to 26 children (for lowercase letters). Insert by walking/creating nodes for each character. Search by walking the tree, if you can follow the entire word and the last node is marked as 'end', the word exists.

Key insight

Use a trie when you need prefix-based operations that hash maps can't do efficiently, like 'find all words starting with X' or 'find word matching pattern with wildcards'.

Common Trie Interview Problems

Implement Trie
Word Search II
Design Add and Search Words
Replace Words
Maximum XOR of Two Numbers

Frequently Asked Questions

Why does a trie need the end-of-word flag at all?

Because a completed walk only proves the characters exist as a path, not that a word ends there. After inserting "apple", the path for "app" exists, yet "app" was never inserted. The boolean on the final node is what distinguishes a stored word from a prefix of one.

Should children be stored in a 26-slot array or a hash map?

An array gives O(1) child access with zero hashing overhead and is ideal for dense lowercase-letter tries. A map wastes no space on absent children, which wins for sparse tries or large alphabets like Unicode. For typical LeetCode constraints the array is the default choice.

When does a trie beat a hash set of strings?

When queries involve prefixes: startsWith, autocomplete, wildcard matching, and shared-prefix compression are natural in a trie and impossible for a hash set without scanning every key. For pure exact-match membership, a hash set is simpler and usually faster in practice.