Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Java - 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 sharing.

Analogy: Imagine a tree of roads where each letter is a turn. Many roads share the same first turns. A trie is like a map showing all shared turns once, while a hash map is like separate maps for each full road.

root
 ↓
 c -> a -> t -> *
      ↓
      r -> *
 d -> o -> g -> *

* marks end of a word

Dry Run Walkthrough

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

Goal: Show how trie shares prefix 'ca' for cat and car, enabling quick prefix search unlike hash map

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

root -> c -> a -> t -> *

Why: We build the path for 'cat' from root, marking end at 't'

Step 2: Insert 'car' sharing 'c' and 'a' nodes, add new node 'r'

root -> c -> a -> t -> *
                 ↓
                 r -> *

Why: Reuse existing prefix nodes to save space and time

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

root -> c -> a -> t -> *
                 ↓
                 r -> *
      ↓
      d -> o -> g -> *

Why: New word with different prefix creates new branch

Step 4: Search prefix 'ca' by following nodes c -> a

root -> [c] -> [a] -> t -> *
                 ↓
                 r -> *
      ↓
      d -> o -> g -> *

Why: Prefix search is fast by following shared nodes

Result:

root -> c -> a -> t -> *
                 ↓
                 r -> *
      ↓
      d -> o -> g -> *
Prefix 'ca' found with words 'cat' and 'car'

Annotated Code

DSA Java

import java.util.*;

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

class Trie {
    private final TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char ch : word.toCharArray()) {
            curr.children.putIfAbsent(ch, new TrieNode()); // create node if missing
            curr = curr.children.get(ch); // move to next node
        }
        curr.isEndOfWord = true; // mark end of word
    }

    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) return false; // prefix missing
            curr = curr.children.get(ch); // move forward
        }
        return true; // prefix found
    }

    public List<String> getWordsWithPrefix(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode curr = root;
        for (char ch : prefix.toCharArray()) {
            if (!curr.children.containsKey(ch)) return results; // no words
            curr = curr.children.get(ch);
        }
        dfs(curr, new StringBuilder(prefix), results);
        return results;
    }

    private void dfs(TrieNode node, StringBuilder path, List<String> results) {
        if (node.isEndOfWord) results.add(path.toString()); // found word
        for (var entry : node.children.entrySet()) {
            path.append(entry.getKey()); // add letter
            dfs(entry.getValue(), path, results); // explore deeper
            path.deleteCharAt(path.length() - 1); // backtrack
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("dog");

        System.out.println("Prefix 'ca' exists: " + trie.startsWith("ca"));
        System.out.println("Words with prefix 'ca': " + trie.getWordsWithPrefix("ca"));
    }
}

curr.children.putIfAbsent(ch, new TrieNode()); // create node if missing

create new node only if letter path missing to share prefixes

curr = curr.children.get(ch); // move to next node

advance current node to next letter node

curr.isEndOfWord = true; // mark end of word

mark node as end of a valid word

if (!curr.children.containsKey(ch)) return false; // prefix missing

stop search early if prefix letter not found

if (node.isEndOfWord) results.add(path.toString()); // found word

collect word when end node reached during DFS

path.append(entry.getKey()); // add letter

add letter to current path during DFS

path.deleteCharAt(path.length() - 1); // backtrack

remove last letter to explore other branches

Output

Prefix 'ca' exists: true

Words with prefix 'ca': [cat, car]

Complexity Analysis

Time: O(m) for insert and prefix search where m is length of word or prefix because we traverse letters once

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

vs Alternative: Hash map stores full strings separately, so prefix search is O(n*m) scanning all keys, while trie shares prefixes for faster prefix queries

Edge Cases

Empty string insertion

Marks root as end of word, allowing empty string search

DSA Java

curr.isEndOfWord = true; // mark end of word

Prefix not present in trie

startsWith returns false immediately when letter missing

DSA Java

if (!curr.children.containsKey(ch)) return false; // prefix missing

Words with shared prefixes

Nodes are reused, saving space and enabling fast prefix search

DSA Java

curr.children.putIfAbsent(ch, new TrieNode()); // create node if missing

When to Use This Pattern

When a problem needs fast prefix search or autocomplete on many strings, reach for trie because it shares prefixes and avoids scanning all keys like hash maps.

Common Mistakes

Mistake: Inserting whole words as separate nodes without sharing prefixes
Fix: Always check and reuse existing child nodes before creating new ones

Mistake: Not marking end of word, causing search to falsely find prefixes as words
Fix: Set isEndOfWord true at last letter node of inserted word

Summary

Stores strings by shared prefixes for fast prefix search.

Use when you need quick prefix queries or autocomplete on many strings.

The key insight is sharing common beginnings saves time and space compared to storing full strings 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 efficiently supports prefix-based searches which Hash Map cannot do directly

B. Because Trie uses less memory than Hash Map for all data types

C. Because Hash Map cannot store strings as keys

D. Because Trie automatically sorts strings alphabetically

Solution

1. Step 1: Understand Trie and Hash Map capabilities

   Trie stores strings in a tree form where each node represents a character, enabling prefix searches. Hash Map stores key-value pairs but does not support prefix queries efficiently.

2. Step 2: Compare prefix search support

   Trie can quickly find all strings starting with a prefix by traversing nodes. Hash Map requires checking each key individually, which is inefficient.

3. Final Answer:

   Because Trie efficiently supports prefix-based searches which Hash Map cannot do directly -> Option A

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 uses less memory always
• Believing Hash Map cannot store strings as keys

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { int[] children = new int[26]; boolean isEndOfWord; }

B. class TrieNode { List<String> children; boolean isEndOfWord; }

C. class TrieNode { String children; boolean isEndOfWord; }

D. class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; }

Solution

1. Step 1: Identify correct data type for children

   Trie node children should map characters to next nodes, so Map is correct.

2. Step 2: Check other options

   class TrieNode { int[] children = new int[26]; boolean isEndOfWord; } uses int array which is possible but not a Map; class TrieNode { String children; boolean isEndOfWord; } uses String which is incorrect; class TrieNode { List<String> children; boolean isEndOfWord; } uses List<String> which is not suitable for child nodes.

3. Final Answer:

   class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; } -> Option D

4. Quick Check:

   Children map = class TrieNode { Map children = new HashMap<>(); boolean isEndOfWord; } [OK]

Hint: Trie children map chars to nodes [OK]

Common Mistakes:

• Using String or List instead of Map for children
• Using int array without explanation
• Forgetting isEndOfWord boolean

3. What will be the output of the following Java code snippet using a Trie?

Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
System.out.println(trie.startsWith("app"));
System.out.println(trie.search("apple"));
System.out.println(trie.search("apples"));

medium

A. true false true

B. false true false

C. true true false

D. false false false

Solution

1. Step 1: Understand insert and search operations

   Inserting "apple" and "app" adds both words. startsWith("app") checks if any word starts with "app" which is true. search("apple") finds exact word, true. search("apples") not inserted, false.

2. Step 2: Evaluate each print statement

   startsWith("app") -> true; search("apple") -> true; search("apples") -> false.

3. Final Answer:

   true true false -> Option C

4. Quick Check:

   Insert + search + prefix check = true true false [OK]

Hint: startsWith true if prefix exists, search true if exact word [OK]

Common Mistakes:

• Confusing startsWith and search results
• Assuming search("apples") returns true
• Mixing order of outputs

4. The following Java code tries to insert strings into a Trie but throws a NullPointerException. What is the likely cause?

class TrieNode {
  Map children;
  boolean isEndOfWord;
}

class Trie {
  TrieNode root = new TrieNode();
  public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
      if (!node.children.containsKey(c)) {
        node.children.put(c, new TrieNode());
      }
      node = node.children.get(c);
    }
    node.isEndOfWord = true;
  }
}

medium

A. children map is not initialized in TrieNode constructor

B. root node is not initialized

C. word.toCharArray() returns null

D. isEndOfWord is not set to false initially

Solution

1. Step 1: Identify NullPointerException source

   NullPointerException likely occurs when calling node.children.containsKey(c) because children map is null.

2. Step 2: Check initialization of children map

   TrieNode class declares children but does not initialize it (e.g., new HashMap<>()), so children is null causing exception.

3. Final Answer:

   children map is not initialized in TrieNode constructor -> Option A

4. Quick Check:

   Uninitialized map = NullPointerException [OK]

Hint: Always initialize children map in TrieNode [OK]

Common Mistakes:

• Assuming root is null
• Thinking toCharArray() returns null
• Ignoring map initialization

5. You want to store a dictionary of 1 million English words and efficiently find all words starting with a given prefix. Why is a Trie better than a Hash Map for this task, and what is a key limitation of Hash Map here?

hard

A. Trie automatically sorts words; Hash Map does not support string keys

B. Trie stores words in a prefix tree allowing fast prefix queries; Hash Map cannot efficiently find keys by prefix without checking all keys

C. Trie uses less memory than Hash Map for large datasets; Hash Map keys must be integers

D. Trie supports deletion of words in O(1); Hash Map deletion is O(n)

Solution

1. Step 1: Understand prefix search requirement

   Finding all words starting with a prefix requires efficient prefix queries, which Trie supports by traversing nodes matching prefix characters.

2. Step 2: Analyze Hash Map limitation

   Hash Map stores keys without order or structure, so to find keys by prefix, it must check all keys, which is slow for large datasets.

3. Final Answer:

   Trie stores words in a prefix tree allowing fast prefix queries; Hash Map cannot efficiently find keys by prefix without checking all keys -> Option B

4. Quick Check:

   Prefix search efficiency = Trie advantage [OK]

Hint: Trie = prefix search; Hash Map = no prefix search [OK]

Common Mistakes:

• Thinking Hash Map keys must be integers
• Assuming Trie uses less memory always
• Confusing deletion complexities