Chapter 17 — Tries (Prefix Trees)

Chapter 17 — Tries (Prefix Trees)

Hey everyone! Welcome back to Namaste DSA!

Ever wondered how your phone's keyboard suggests words so fast, or how a search box autocompletes as you type? The answer is often a Trie (pronounced "try"), a tree that stores words letter by letter and shares common prefixes.

What we will cover:

• How a trie stores words letter by letter
• Insert and search
• Prefix search (autocomplete!)
• When a trie beats a hash map
• Interview Questions

---

1. How a Trie Stores Words

Each node represents one character. Following a path from the root spells out a word. Words sharing a prefix share the same path until they diverge.

┌─────────────────────────────────────────────────────────────┐
│   Inserted: "cat", "car", "card", "dog"                     │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│            (root)                                           │
│            /     \                                          │
│          c        d                                         │
│          │        │                                         │
│          a        o                                         │
│         / \       │                                         │
│        t   r      g●        ● = end of a word              │
│        ●   │●                                              │
│            d●                                              │
│                                                             │
│   "cat" & "car" & "card" share the "ca" path!              │
└─────────────────────────────────────────────────────────────┘

---

2. Insert & Search

class TrieNode {
    constructor() {
        this.children = {};       // char → TrieNode
        this.isEnd = false;       // marks end of a complete word
    }
}

class Trie {
    constructor() { this.root = new TrieNode(); }

    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children[c]) node.children[c] = new TrieNode();
            node = node.children[c];
        }
        node.isEnd = true;        // mark the last node
    }

    search(word) {
        const node = this._walk(word);
        return node !== null && node.isEnd;   // must be a FULL word
    }

    startsWith(prefix) {
        return this._walk(prefix) !== null;   // any path is enough
    }

    _walk(str) {
        let node = this.root;
        for (const c of str) {
            if (!node.children[c]) return null;
            node = node.children[c];
        }
        return node;
    }
}

Key distinction: search("car") needs isEnd === true (a complete word), but startsWith("car") just needs the path to exist.

---

3. Complexity — It's About Word Length, Not Word Count

┌─────────────────────────────────────────────────────────────┐
│   Insert / Search / Prefix check  →  O(L)                   │
│   where L = length of the word/prefix                       │
│                                                             │
│   It does NOT depend on how many words are stored!          │
│   A trie with 1 million words searches just as fast as      │
│   one with 10 words — only the word's length matters.       │
└─────────────────────────────────────────────────────────────┘

---

4. Prefix Search — Autocomplete

Walk to the end of the prefix, then DFS to collect all words below it.

function autocomplete(trie, prefix) {
    const node = trie._walk(prefix);
    if (!node) return [];
    const results = [];
    (function dfs(curr, path) {
        if (curr.isEnd) results.push(path);
        for (const c in curr.children) dfs(curr.children[c], path + c);
    })(node, prefix);
    return results;
}
// autocomplete(trie, "car") → ["car", "card"]

---

5. When a Trie Beats a Hash Map

	Hash Map (Set of words)	Trie
Exact lookup	O(L) avg	O(L)
Prefix search	O(n·L) — scan everything ✗	O(L + matches) ✔
Shared prefixes	Stored separately (more memory)	Shared (saves memory)
Sorted/ordered output	No	Yes (DFS in order)

Use a trie when you need prefix operations — autocomplete, spell-check, word games, IP routing. For plain "is this exact word present?", a hash set is simpler.

---

Interview Questions — Quick Fire!

Q: What is a trie and what is it good for?

"A trie is a tree where each node is a character and each path from the root spells a word, with shared prefixes stored once. It excels at prefix operations like autocomplete and spell-check, where insert, search, and prefix-check are all O(L) in the word length."

Q: What's the time complexity of trie operations?

"O(L) where L is the length of the word or prefix — independent of how many words are stored. That's its big advantage: a trie with a million words is just as fast to query as one with ten."

Q: How do you distinguish a full word from a prefix in a trie?

"Each node has an isEnd flag. Search returns true only if you reach the end of the word and isEnd is set, while startsWith just checks that the path exists. Without the flag, 'car' would falsely match when only 'card' was inserted."

Q: When would you use a trie over a hash set?

"When you need prefix queries. A hash set would have to scan every word to find those with a given prefix — O(n·L) — whereas a trie walks straight to the prefix node and collects matches in O(L + number of matches). Tries also save memory by sharing common prefixes."

---

Quick Recap

Concept	Key Takeaway
Structure	Tree of characters; paths spell words.
isEnd flag	Marks a complete word vs a prefix.
Complexity	O(L) — word length, not word count.
Prefix search	Walk to prefix, DFS to collect.
vs hash set	Trie wins on prefixes & shared memory.

What's Next?

Chapter 18 closes Season 4 with the big one: Graphs — representation, plus BFS and DFS, the two traversals that unlock shortest paths, connectivity, and cycle detection.

Keep coding, keep grinding! See you in the next one!