Trie Data Structure
Session Notes

Tree of characters; root is empty; path root→node = prefix; flag marks end of word.

• node = { TrieNode[] children (size = alphabet); boolean isEnd }
• ⭐ Universal recipe → insert ALL words first, then search.
• index = ch − 'a' (lowercase) picks the child slot.
• insert O(L) · search O(L) · space O(N·M) [+ ×alphabet const].
• doodle: root → [c]→[a]→[t]● branching to [b]→[a]→[t]●

Insight: the reference template — memorize insert + search verbatim, everything else reuses it.

Time O(L) insert & search · Space O(N·M).

insert(w): p=root; for c in w: if !p.ch[c] p.ch[c]=new; p=p.ch[c]; p.isEnd=true
search(w): p=root; for c in w: if !p.ch[c] return false; p=p.ch[c]; return p.isEnd

Practice: LeetCode 208 — Implement Trie (Prefix Tree)

Insight: a word qualifies only if EVERY node on its path is isEnd=true. Tie → lexicographically smallest.

Time O(total chars) · Space O(N·M).

insert all words
for w in words: walk w; if any node !isEnd → skip
  if len>best OR (len== && w<best): best=w
return best  // "" if none

Practice: GeeksforGeeks — Longest Valid Word with All Prefixes · variant LeetCode 720

Insight: BFS over start-indices; a queue holds trie nodes, each dictionary-word end spawns a fresh restart from root. Visited[] on start-index kills re-work.

Time O(n²) worst · Space O(n + trie).

insert dict; q={root}; visited[start]
while q && start<n: for node in level:
  if node.ch[s[start]]: q.add child
  if child.isEnd && !visited[start]: q.add root; visited[start]=true
  start++ (when level drained)
return start==n && visited[n-1]

Practice: LeetCode 139 — Word Break

Insight: insert each row into a trie of children[2]; if insert finds the leaf already marked, that row is a duplicate — search + insert in one pass.

Time O(rows·cols) · Space O(rows·cols).

for i,row in matrix:
  if !insert(root,row): print(i+1)  // insert returns false if isLeaf already set
insert: walk bits; if end.isLeaf return false; end.isLeaf=true; return true

Practice: GeeksforGeeks — Duplicate Rows in a Binary Matrix

A trie stores a dynamic set of strings as a tree of characters. The root is empty; each edge is one character; each node represents the prefix formed by the path from the root. A complete word is recognized by a boolean isEnd flag on the node where it terminates — not by being a leaf, because one word can be a prefix of another.

Children count is fixed by the alphabet. Ask the interviewer whether input is lowercase only (26), both cases (52), digits, etc. This bound is what makes the trie efficient — the branching factor is a constant, not input-dependent.

• ⭐ TRICK — the universal recipe. In any trie problem: insert every input word first, then perform the search/traversal on that single trie. Almost every problem below is a variation on this one shape.
• 💡 TIP — trie shines for search + prefix matching. When a problem says "search", "prefix", or "starts with", reach for a trie. Its payoff is O(L) lookup regardless of how many words you stored.
• ⚠ PITFALL — end-of-word ≠ leaf. Mark words with isEnd, not by checking for a leaf. "cat" and "cattle" share a path; the node after "cat" has a child yet is still a valid word end.
• 💡 TIP — index = ch - 'a'. Subtracting 'a' maps a lowercase char to a 0–25 array slot. Use 'A' for uppercase; size the array to match the declared alphabet.

Complexity. Insert and search are each O(L) where L = word length. Trie space is O(N·M) where N = number of words, M = longest word (this is the height contribution). The per-node alphabet array (26/52) is a constant factor and drops out of big-O — though it does make the trie memory-heavy in practice.

Reference template (Java).

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';   // slot for this char
            if (cur.children[idx] == null) cur.children[idx] = new TrieNode();
            cur = cur.children[idx];
        }
        cur.isEndOfWord = true;               // mark the terminal node
    }

    boolean search(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (cur.children[idx] == null) return false;  // char path missing
            cur = cur.children[idx];
        }
        return cur.isEndOfWord;               // present only if flagged
    }
}

Why this matters: every problem below is these two methods, lightly modified. Internalize them and the rest is recognition.

Build a trie supporting insert(word) and search(word). Standard prefix-tree implementation; the foundation for everything else.

Practice: LeetCode 208 — Implement Trie (Prefix Tree). [!] LeetCode 208 also requires startsWith(prefix), which isn't covered above; it's a trivial variant of search that returns true after the walk instead of checking isEnd.

Pattern / family: Trie construction. This is the "hello world" of the prefix-tree family.

Approach — there is no brute-force worth doing. A hash set gives O(1) exact lookup but cannot answer prefix queries; the trie's advantage is O(L) prefix and word search over a single shared structure. Core idea: walk the word char-by-char, creating missing nodes on insert, failing fast on a missing child during search.

• Insert: from root, follow/create the child for each char, then set isEndOfWord = true on the last node. O(L).
• Search: from root, follow each char; if any child is null return false; after the walk return the last node's isEndOfWord. O(L).

Java (optimal). Uses alphabetSize = 26; see the reference template above — LeetCode 208's canonical form is identical, plus a startsWith that skips the final isEnd check.

boolean startsWith(String prefix) {   // [+] LeetCode 208 requires this
    TrieNode cur = root;
    for (int i = 0; i < prefix.length(); i++) {
        int idx = prefix.charAt(i) - 'a';
        if (cur.children[idx] == null) return false;
        cur = cur.children[idx];
    }
    return true;   // reached end of prefix → some word has it
}

• ⚠ PITFALL — returning true too early in search. After consuming all chars you must still check isEndOfWord. Reaching the last node only proves the prefix exists, not the full word.
• Edge cases: empty string (root's own isEnd); repeated inserts (idempotent); searching a prefix that isn't a stored word (returns false via the flag).

Complexity: insert O(L), search O(L); space O(N·M). Why this matters: the two-method skeleton transfers directly to problems 2–4.

Given an array of words, find the longest word such that every one of its prefixes is also in the array; on a length tie return the lexicographically smallest. Return "" if none.

Practice: GeeksforGeeks — Longest Valid Word with All Prefixes. Not on LeetCode; the close variant is LeetCode 720 "Longest Word in Dictionary" (same idea, ties broken by smallest word).

Pattern / family: Trie + prefix validation. Recognize it whenever "every prefix must also exist" appears.

Example. For {k, ki, kir, kira, kiran, cricket}: "kiran" has prefixes k, ki, kir, kira, kiran — all present → valid answer. "cricket" fails because its prefix "c" (and others) are absent.

Approach. Insert all words. Then for each word, walk its path in the trie; if every node along the way is isEndOfWord, the word is a candidate. Keep the best by (longer length) then (lexicographically smaller).

• ⭐ TRICK — validity = all-nodes-are-word-ends. You don't re-search each prefix separately. Walking the word once and confirming every intermediate node has isEnd=true proves all prefixes exist in a single O(L) pass.
• 💡 TIP — no sorting needed for ties. Keep a result string; when a new candidate ties on length, compare with result.compareTo(word) > 0 and keep the smaller. Avoids a separate sort pass.
• ⚠ PITFALL — comparing lengths only. Forgetting the lexicographic tie-break gives wrong answers when two valid words share the max length.

Java (optimal). [!] One version uses children[128] (size it 26/52/60 as needed); 26 is correct for lowercase-only input. Shown with 26.

class Solution {
    TrieNode root = new TrieNode();
    String result = "";

    String longestString(String[] words) {
        for (String w : words) addWord(w);       // insert phase
        for (String w : words) searchPrefix(w);  // validate phase
        return result;
    }

    void addWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) cur.children[idx] = new TrieNode();
            cur = cur.children[idx];
        }
        cur.isEndOfWord = true;
    }

    void searchPrefix(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (!cur.isEndOfWord) return;         // a prefix is missing → reject
        }
        // whole word valid: keep longest, tie → lexicographically smallest
        if (word.length() > result.length() || (word.length() == result.length() && result.compareTo(word) > 0)) {
            result = word;
        }
    }
}

• Edge cases: no valid word → ""; single-char words are always valid if present; duplicates are harmless.
• Follow-up raised: could you walk the trie a→z instead of scanning words, to hit the lexicographically smallest first? Yes — a DFS in sorted child order naturally yields the smallest, but the result-compare approach is simpler and equally correct.

Complexity: O(total characters) build + validate; space O(N·M). Why this matters: "walk once, check a flag at every node" is a reusable trie idiom (autocomplete, staged-word validation).

Given a string s and a dictionary, return true if s can be segmented into a space-free sequence of dictionary words (words reusable).

Practice: LeetCode 139 — Word Break.

Pattern / family: String segmentation. These notes solve it with a trie + BFS over start-positions; the mainstream solution is DP.

Examples. s="applepenapple", dict {apple, pen} → true ("apple"+"pen"+"apple", apple reused). s="catsandog", dict {cats, dog, sand, and, cat} → false: every split leaves an "og" that isn't in the dictionary.

Approach — BFS over cut positions. Insert the dictionary into a trie. BFS where each frontier item is a trie node being matched from some start index. Advancing a character moves to a child; whenever a child is isEndOfWord and that start index hasn't been used, you've completed a word — enqueue a fresh root to begin the next word and mark the start index visited. Succeed if you consume the whole string.

• ⭐ TRICK — visited[] on start-index prevents exponential blow-up. Many paths reach the same cut position; marking a start index visited means you never re-explore segmentations from there. This is the memoization that turns brute-force recursion into polynomial time.
• 💡 TIP — enqueue root on each word end. Finishing a word resets matching to the trie root, because the next segment is a brand-new dictionary lookup. That "restart from root" is the whole trick to chaining words.
• ⚠ PITFALL — this is fundamentally a DP problem. DP is a natural fit here alongside the trie/BFS; note that the widely-taught optimal is DP (dp[i] = "s[0..i] segmentable"). Both are valid — know the DP form for interviews.
• ⚠ PITFALL — same start index reused. Without the visited guard you'd re-enqueue root for the same index repeatedly and loop.

Java — mainstream DP (recommended for interviews) [+]. O(n²) time (O(n³) if you count substring cost), O(n) space. Clearer to reason about than the BFS.

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);   // O(1) lookup
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;                                  // empty prefix is segmentable
    for (int end = 1; end <= n; end++) {
        for (int start = 0; start < end; start++) {
            if (dp[start] && dict.contains(s.substring(start, end))) {
                dp[end] = true;                    // s[0..end) segmentable
                break;
            }
        }
    }
    return dp[n];
}

Java — trie + BFS.

boolean wordBreak(String s, List<String> wordDict) {
    TrieNode trie = new TrieNode();
    for (String w : wordDict) insert(w, trie);
    return helper(s.toCharArray(), 0, trie);
}

boolean helper(char[] arr, int start, TrieNode root) {
    Queue<TrieNode> q = new LinkedList<>();
    q.add(root);
    boolean[] visited = new boolean[arr.length];
    while (!q.isEmpty() && start < arr.length) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TrieNode t = q.poll();
            int idx = arr[start] - 'a';
            if (t.children[idx] != null) {
                q.add(t.children[idx]);
                if (t.children[idx].isEndOfWord && !visited[start]) {
                    q.add(root);              // word done → restart matching
                    visited[start] = true;
                }
            }
        }
        if (!q.isEmpty()) start++;            // advance to next char
    }
    return start == arr.length && visited[arr.length - 1];
}

• Edge cases: empty s → true; single char both in/out of dict; heavy reuse (all same letter) stresses the visited guard.
• Follow-ups: Word Break II (return all segmentations — needs backtracking, not just a boolean); why not DP here (it is the standard answer — the trie version demonstrates trie flexibility).

Complexity: DP O(n²)/O(n); BFS bounded by n start-positions × trie depth, ~O(n²) worst, plus O(dict) trie space. Why this matters: "visited on position + BFS/DP over indices" recurs across segmentation and reachability problems.

Given a binary matrix, report the duplicate rows (rows equal to an earlier row), traversing the matrix only once. Output the 1-based indices of the duplicates.

Practice: GeeksforGeeks — Duplicate Rows in a Binary Matrix. Not on LeetCode.

Pattern / family: Trie as a set/dedup structure. Each row is treated like a "word" over the alphabet {0, 1}.

Example. Rows [1 0 0 1 0], [0 1 1 0 0], [1 0 0 1 0], [0 0 1 0 0], [0 1 1 0 0] → duplicates at rows 3 and 5 (repeats of rows 1 and 2).

Approach. Since cells are 0/1, each node needs only children[2]. Insert each row bit-by-bit. If, after walking a row, the terminal node is already flagged (isLeaf/isEnd already true), the row was inserted before → it's a duplicate.

• ⭐ TRICK — insert IS the search. Make insert return false when the row's end node is already marked. One pass detects duplicates without a separate search step or a hash of stringified rows.
• 💡 TIP — branching factor is just 2. Binary input collapses the alphabet to {0,1}, so the trie is a binary tree of depth = number of columns. Interviewers set the alphabet deliberately to control space.
• ⚠ PITFALL — memory. A trie can hold up to (branching)^depth nodes worst case; here 2^cols. For larger alphabets (26^height) this is why interviewers cap the character set. It buys O(L) search at the cost of space.

Java (optimal).

class TrieNode {
    boolean isLeaf;                       // true once a full row ends here
    TrieNode[] child = new TrieNode[2];   // only 0 and 1
}

static boolean insert(TrieNode head, int[] row) {
    TrieNode cur = head;
    for (int bit : row) {
        if (cur.child[bit] == null) cur.child[bit] = new TrieNode();
        cur = cur.child[bit];
    }
    if (cur.isLeaf) return false;         // row already present → duplicate
    cur.isLeaf = true;
    return true;
}

static void printDuplicateRows(int[][] matrix) {
    TrieNode head = new TrieNode();
    for (int i = 0; i < matrix.length; i++) {
        if (!insert(head, matrix[i]))     // false → duplicate
        System.out.println(i + 1);    // 1-based row number
    }
}

• Edge cases: all rows identical (every row after the first is a duplicate); single row (never duplicate); 1-based vs 0-based output — return i + 1.
• Follow-up: alternative is hashing each row (e.g., as a string or bitmask) into a HashSet — O(rows·cols) time, often less memory; the trie shows the same result via structure.

Complexity: O(rows·cols) time (single traversal), O(rows·cols) space worst case. Why this matters: a trie is a general dedup/membership structure — "insert returns whether it was new" generalizes to any fixed-alphabet key.

Problem	Technique	Key insight	Time / Space
Implement Trie	Trie template	Insert creates nodes + flags end; search fails on null child, then checks isEnd	O(L) / O(N·M)
Longest word w/ all prefixes	Trie prefix-walk	Word valid iff every node on its path is isEnd; tie → lexicographically smallest	O(ΣL) / O(N·M)
Word Break	Trie + BFS (or DP)	BFS over start-indices, restart at root on each word end; visited[] = memoization	O(n²) / O(n + dict)
Duplicate rows in binary matrix	2-child trie / dedup	Insert returns false if end node already flagged → duplicate in one pass	O(R·C) / O(R·C)

The through-line: build one trie by inserting all inputs, then let a single traversal answer the question — searching, validating prefixes, chaining words, or detecting repeats. Fix the child-array size to the declared alphabet, mark word ends with a flag (never rely on "leaf"), and remember that a trie trades memory for O(L) lookup.