Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Python - Why This Pattern

Mental Model

A trie stores strings by sharing common beginnings, making prefix searches fast and memory efficient. Hash maps store whole strings separately, missing this shared structure.

Analogy: Imagine a tree of roads where each letter is a turn. Many roads share the same first turns before splitting. A trie is like this road map, saving space by sharing paths. A hash map is like separate maps for each road, repeating the same first turns over and over.

root
 ├─ c
 │  ├─ a
 │  │  ├─ t (end)
 │  │  └─ r (end)
 │  └─ o
 │     └─ w (end)
 └─ d
    └─ o
       └─ g (end)

Dry Run Walkthrough

Input: Insert words: 'cat', 'car', 'cow', 'dog'; then search prefix 'ca'

Goal: Show how trie shares prefixes for fast prefix search, unlike hash map

Step 1: Insert 'cat' letter by letter creating new nodes

root -> c -> a -> t[end]

Why: We build the path for 'cat' from root to t

Step 2: Insert 'car' sharing 'c' and 'a', then add 'r'

root -> c -> a -> t[end], r[end]

Why: Reuse existing nodes for 'c' and 'a' to save space

Step 3: Insert 'cow' sharing 'c', add 'o' and 'w'

root -> c -> a -> t[end], r[end]; c -> o -> w[end]

Why: Share prefix 'c' but branch at second letter

Step 4: Insert 'dog' creating new branch from root

root -> c -> a -> t[end], r[end]; c -> o -> w[end]; d -> o -> g[end]

Why: New word starts with 'd', so new branch needed

Step 5: Search prefix 'ca' by following nodes 'c' then 'a'

At node 'a' with children 't' and 'r'

Why: Prefix search finds all words starting with 'ca' quickly

Result:

root -> c -> a -> t[end], r[end]; c -> o -> w[end]; d -> o -> g[end]
Prefix 'ca' found with words: 'cat', 'car'

Annotated Code

DSA Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # create node if missing
            node = node.children[char]  # move to child node
        node.is_end = True  # mark end of word

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False  # prefix missing
            node = node.children[char]  # move to next node
        return True  # prefix found

    def collect_words(self, node=None, prefix='', words=None):
        if words is None:
            words = []
        if node is None:
            node = self.root
        if node.is_end:
            words.append(prefix)  # found a word
        for char, child in node.children.items():
            self.collect_words(child, prefix + char, words)  # recurse children
        return words

# Driver code
trie = Trie()
words = ['cat', 'car', 'cow', 'dog']
for w in words:
    trie.insert(w)

prefix = 'ca'
found = trie.starts_with(prefix)
collected = trie.collect_words()
print(f"Prefix '{prefix}' found: {found}")
print(f"All words in trie: {', '.join(collected)}")

if char not in node.children: node.children[char] = TrieNode() # create node if missing

create new node only if letter path missing to share prefixes

node = node.children[char] # move to child node

advance pointer to next letter node

node.is_end = True # mark end of word

mark node as end of a valid word

if char not in node.children: return False # prefix missing

stop search if prefix letter missing

if node.is_end: words.append(prefix) # found a word

collect words when end node reached

Output

Prefix 'ca' found: True

All words in trie: cat, car, cow, dog

Complexity Analysis

Time: O(m) per insert or search, where m is length of the word or prefix, because we process each letter once

Space: O(n*m) in worst case for n words of length m, but shared prefixes reduce actual space

vs Alternative: Hash maps store full strings separately, so prefix search is O(n*m) scanning all keys, while trie does prefix search in O(m)

Edge Cases

Empty string insertion

Marks root as end of word, allowing empty string search

DSA Python

node.is_end = True  # mark end of word

Prefix not present

Search returns False immediately when letter missing

DSA Python

if char not in node.children:
    return False  # prefix missing

Words with shared prefixes

Nodes are reused, saving space and enabling fast prefix search

DSA Python

if char not in node.children:
    node.children[char] = TrieNode()  # create node if missing

When to Use This Pattern

When you need to quickly find all words sharing a prefix or do prefix-based queries, reach for the trie pattern because hash maps cannot efficiently share prefixes or do prefix searches.

Common Mistakes

Mistake: Trying to use a hash map for prefix search by scanning all keys
Fix: Use a trie to share prefixes and enable O(m) prefix search instead of scanning all keys

Summary

A trie stores strings by sharing common prefixes for efficient prefix search.

Use tries when you need fast prefix queries or to save space by sharing prefixes.

The key insight is that tries share nodes for common prefixes, unlike hash maps that store full keys separately.

Practice

1. Why do we use a Trie data structure instead of a Hash Map for storing a large set of strings?

easy

A. Because Trie uses less memory than Hash Map always

B. Because Trie supports efficient prefix search which Hash Map cannot do easily

C. Because Hash Map cannot store strings as keys

D. Because Trie is faster for all types of lookups

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form allowing prefix-based queries efficiently. Hash Map stores keys but does not support prefix search directly.

2. Step 2: Compare prefix search ability

   Hash Map can check full keys but cannot find all keys with a given prefix efficiently. Trie can find all keys sharing a prefix quickly.

3. Final Answer:

   Because Trie supports efficient prefix search which Hash Map cannot do easily -> Option B

4. Quick Check:

   Prefix search = Trie advantage [OK]

Hint: Trie is for prefix search; Hash Map is not [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Assuming Trie always uses less memory
• Believing Hash Map cannot store string keys

2. Which of the following is the correct way to initialize a Trie node in Python?

easy

A. node = set()

B. node = []

C. node = {'children': {}, 'is_end': False}

D. node = ''

Solution

1. Step 1: Identify Trie node structure

   A Trie node typically has a dictionary for children and a boolean to mark end of word.

2. Step 2: Match with options

   node = {'children': {}, 'is_end': False} correctly uses a dictionary for children and a boolean flag. Others do not represent Trie node structure.

3. Final Answer:

   node = {'children': {}, 'is_end': False} -> Option C

4. Quick Check:

   Trie node = dict + bool [OK]

Hint: Trie node needs children dict and end flag [OK]

Common Mistakes:

• Using list or set instead of dictionary for children
• Not including end-of-word marker
• Using empty string as node

3. What will be the output of the following code snippet?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

trie = Trie()
trie.insert('cat')
trie.insert('car')
print(trie.search('cat'))
print(trie.search('ca'))
print(trie.search('car'))

medium

A. True\nFalse\nTrue

B. True\nTrue\nTrue

C. False\nFalse\nFalse

D. True\nFalse\nFalse

Solution

1. Step 1: Insert words 'cat' and 'car'

   Both words are inserted character by character, marking end of word at last character.

2. Step 2: Search for 'cat', 'ca', and 'car'

   'cat' and 'car' exist fully with end marked True, so search returns True. 'ca' is prefix but not end of word, so returns False.

3. Final Answer:

   True\nFalse\nTrue -> Option A

4. Quick Check:

   Search full word only returns true [OK]

Hint: Search returns true only if full word inserted [OK]

Common Mistakes:

• Assuming prefix search returns true
• Confusing is_end flag usage
• Not updating node during insert

4. The following code tries to insert words into a Trie but has a bug. What is the bug?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for char in word:
            if char in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

medium

A. It does not initialize the root node

B. It never marks the end of word

C. It uses list instead of dictionary for children

D. It overwrites existing child nodes instead of checking if they exist

Solution

1. Step 1: Analyze insert method condition

   The code checks if char is in children, then overwrites with new TrieNode, which erases existing nodes.

2. Step 2: Identify correct logic

   It should add new TrieNode only if char NOT in children, to avoid overwriting existing nodes.

3. Final Answer:

   It overwrites existing child nodes instead of checking if they exist -> Option D

4. Quick Check:

   Insert overwrites nodes = bug [OK]

Hint: Add node only if child missing, not if present [OK]

Common Mistakes:

• Confusing if condition logic
• Forgetting to mark end of word
• Not initializing root node

5. You want to find all words in a dictionary that start with the prefix 'pre'. Why is a Trie better than a Hash Map for this task, and how would you implement the prefix search?

hard

A. Trie stores words in a tree allowing prefix traversal; implement by walking nodes for prefix then collecting all descendants

B. Hash Map stores keys with prefix indexing; implement by filtering keys starting with prefix

C. Trie hashes prefixes for quick lookup; implement by hashing prefix and returning matches

D. Hash Map stores words sorted; implement by binary search on keys

Solution

1. Step 1: Understand prefix search in Trie vs Hash Map

   Trie organizes words by characters in a tree, enabling direct traversal to prefix node. Hash Map keys are unordered, so prefix search requires scanning all keys.

2. Step 2: Describe prefix search implementation in Trie

   Traverse Trie nodes for each prefix character, then recursively collect all words from that node's descendants.

3. Final Answer:

   Trie stores words in a tree allowing prefix traversal; implement by walking nodes for prefix then collecting all descendants -> Option A

4. Quick Check:

   Prefix search = Trie traversal + collect descendants [OK]

Hint: Trie prefix search = walk prefix + gather words [OK]

Common Mistakes:

• Thinking Hash Map can do prefix search efficiently
• Confusing hashing with prefix traversal
• Assuming keys in Hash Map are sorted