DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Time & Space Complexity Common Mistakes Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Trie

What Is a Trie?

A Trie (also called a prefix tree or digital tree) is a tree where each node represents a character in a string. A path from the root to any node spells out a prefix. A path ending at a node marked as isEndOfWord = true spells a complete stored word.

Trie storing: ["cat", "car", "card", "care", "bat", "ball"]

              (root)
             /      \
            c        b
            |        |
            a        a
           / \      / \
          t   r    t   l
          *   |    *   |
             / \       l
            d   e      *
            *   *

  * = isEndOfWord = true (complete word ends here)

PATHS:
  root → c → a → t*           = "cat"   ✓
  root → c → a → r → d*       = "card"  ✓
  root → c → a → r → e*       = "care"  ✓
  root → c → a → r            = "car"*  ← BUT is "car" stored? Not in this example.
  root → b → a → t*           = "bat"   ✓
  root → b → a → l → l*       = "ball"  ✓

SHARED PREFIXES:
  "cat" and "car" and "card" and "care" share c → a
  Stored ONCE — that's why tries are space-efficient for related words.

Trie Node Structure

TRIE NODE:
  ┌─────────────────────────────────────────────┐
  │ children: Node[26]    or  Map<char, Node>   │
  │   children['a'-'a'] = pointer to 'a' child  │
  │   children['b'-'a'] = pointer to 'b' child  │
  │   ...                                        │
  │   null if no child for that character        │
  │                                              │
  │ isEndOfWord: boolean                         │
  │   true  = a complete word ends at this node  │
  │   false = only a prefix passes through here  │
  └─────────────────────────────────────────────┘

COMPARISON: array[26] vs HashMap

  array[26]:              HashMap<char, Node>:
  ✓ O(1) exact access     ✓ Space proportional to actual children
  ✓ Simple implementation ✓ Handles any character set (Unicode, digits)
  ✗ 26 slots per node     ✗ Slightly higher constant for hash lookup
    (even if only 1 used)

  Use array[26] for: lowercase a-z only (standard interview setting)
  Use HashMap for:   case-sensitive, mixed types, large alphabets

Complete Trie Implementation

Java

import java.util.*;

public class Trie {

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

    private final TrieNode root = new TrieNode();

    // INSERT word — O(L) where L = word length
    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();   // Create node if missing
            }
            curr = curr.children[idx];
        }
        curr.isEndOfWord = true;   // Mark end of word
    }

    // SEARCH — returns true only if exact word is stored — O(L)
    public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEndOfWord;
    }

    // STARTS WITH — returns true if any stored word has this prefix — O(L)
    public boolean startsWith(String prefix) {
        return getNode(prefix) != null;   // Path exists (don't need isEndOfWord)
    }

    // Helper: traverse to the node at end of string (or null if path missing)
    private TrieNode getNode(String s) {
        TrieNode curr = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) return null;  // Path broken
            curr = curr.children[idx];
        }
        return curr;
    }

    // DELETE word — O(L)
    public boolean delete(String word) {
        return deleteHelper(root, word, 0);
    }

    private boolean deleteHelper(TrieNode node, String word, int depth) {
        if (node == null) return false;   // Word not found

        if (depth == word.length()) {
            if (!node.isEndOfWord) return false;   // Word not in trie
            node.isEndOfWord = false;
            return !hasChildren(node);   // Can this node be deleted?
        }

        int idx = word.charAt(depth) - 'a';
        boolean shouldDelete = deleteHelper(node.children[idx], word, depth + 1);

        if (shouldDelete) {
            node.children[idx] = null;   // Remove reference
            return !node.isEndOfWord && !hasChildren(node);
        }

        return false;
    }

    private boolean hasChildren(TrieNode node) {
        for (TrieNode child : node.children)
            if (child != null) return true;
        return false;
    }

    // COUNT words with given prefix — O(subtree size)
    public int countWordsWithPrefix(String prefix) {
        TrieNode node = getNode(prefix);
        if (node == null) return 0;
        return countWords(node);
    }

    private int countWords(TrieNode node) {
        int count = node.isEndOfWord ? 1 : 0;
        for (TrieNode child : node.children)
            if (child != null) count += countWords(child);
        return count;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat"); trie.insert("car"); trie.insert("card");
        trie.insert("care"); trie.insert("bat"); trie.insert("ball");

        System.out.println(trie.search("cat"));          // true
        System.out.println(trie.search("car"));          // false (not inserted!)
        System.out.println(trie.search("card"));         // true
        System.out.println(trie.startsWith("ca"));       // true
        System.out.println(trie.startsWith("xyz"));      // false

        System.out.println(trie.countWordsWithPrefix("ca")); // 3 (cat, card, care)
        System.out.println(trie.countWordsWithPrefix("ba")); // 2 (bat, ball)

        trie.delete("card");
        System.out.println(trie.search("card"));         // false
        System.out.println(trie.search("care"));         // true (care still exists)
    }
}

Output:
true
false
true
true
false
3 (cat, card, care)
2 (bat, ball)
false (card deleted)
true  (care still exists)

Operations Traced

Insert "care" into existing trie with "cat", "car", "card"

Existing paths: root→c→a→t*, root→c→a→r→d*

Insert "care":
  c: root.children['c'-'a'] exists → follow
  a: c.children['a'-'a'] exists → follow
  r: a.children['r'-'a'] exists → follow
  e: r.children['e'-'a'] is null → CREATE new node
  At new 'e' node: set isEndOfWord = true

Before:               After:
root→c→a→t*           root→c→a→t*
         r→d*                  r→d*
                                 e*   ← new

Search "car" (not inserted as a word)

Traverse: root→c→a→r
  All characters found — path exists ✓
  BUT node 'r' has isEndOfWord = false
  → return false   ("car" prefix exists but is not a word)

Search "cab":
  root→c→a found, then 'b'
  a.children['b'-'a'] = null → path breaks
  → return false

Application 1: Autocomplete

Given a prefix, return all words in the trie that start with it.

Trie: ["cat","car","card","care","bat","ball"]
Autocomplete("ca") → ["cat","card","care"]
Autocomplete("ba") → ["bat","ball"]
Autocomplete("xyz") → []

ALGORITHM:
  1. Navigate to the prefix node (same as startsWith)
  2. DFS the subtree — collect every path that reaches isEndOfWord=true

Java

import java.util.*;

public class Autocomplete {

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

    static class AutocompleteTrie {
        TrieNode root = new TrieNode();

        void insert(String word) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new TrieNode();
                curr = curr.children[i];
            }
            curr.isEnd = true;
        }

        List<String> autocomplete(String prefix) {
            List<String> results = new ArrayList<>();
            TrieNode curr = root;

            // Navigate to prefix end
            for (char c : prefix.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) return results;  // Prefix not found
                curr = curr.children[i];
            }

            // DFS from prefix node — collect all complete words
            collectWords(curr, new StringBuilder(prefix), results);
            return results;
        }

        private void collectWords(TrieNode node, StringBuilder path, List<String> results) {
            if (node.isEnd) results.add(path.toString());

            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null) {
                    path.append((char)('a' + i));
                    collectWords(node.children[i], path, results);
                    path.deleteCharAt(path.length() - 1);   // Backtrack
                }
            }
        }
    }

    public static void main(String[] args) {
        AutocompleteTrie trie = new AutocompleteTrie();
        for (String w : new String[]{"cat","car","card","care","bat","ball"})
            trie.insert(w);

        System.out.println(trie.autocomplete("ca"));   // [cat, card, care]
        System.out.println(trie.autocomplete("ba"));   // [ball, bat]
        System.out.println(trie.autocomplete("car"));  // [card, care]
        System.out.println(trie.autocomplete("xyz"));  // []
    }
}

Output:
["cat", "card", "care"]
["ball", "bat"]
["card", "care"]
[]

Application 2: Wildcard Search (Word Dictionary)

Support '.' which matches any single character. DFS through all children at wildcard positions.

Dictionary: ["bad","dad","mad"]
search("pad") → false  (no word starting with 'p')
search("bad") → true
search(".ad") → true   ('.' matches 'b','d','m')
search("b..") → true   ('b' then any two chars = 'bad')

ALGORITHM:
  Regular character → follow single child
  '.' → recurse into ALL non-null children

Java

public class WordDictionary {

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }

    private final TrieNode root = new TrieNode();

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

    public boolean search(String word) {
        return searchHelper(root, word, 0);
    }

    private boolean searchHelper(TrieNode node, String word, int idx) {
        if (idx == word.length()) return node.isEnd;

        char c = word.charAt(idx);

        if (c != '.') {
            // Regular character — follow single child
            TrieNode next = node.children[c - 'a'];
            return next != null && searchHelper(next, word, idx + 1);
        } else {
            // Wildcard — try ALL children
            for (TrieNode child : node.children) {
                if (child != null && searchHelper(child, word, idx + 1)) {
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        WordDictionary dict = new WordDictionary();
        dict.addWord("bad"); dict.addWord("dad"); dict.addWord("mad");

        System.out.println(dict.search("pad"));  // false
        System.out.println(dict.search("bad"));  // true
        System.out.println(dict.search(".ad"));  // true  (b/d/m + ad)
        System.out.println(dict.search("b.."));  // true  (b + a + d)
        System.out.println(dict.search("..."));  // true  (any 3 chars = bad/dad/mad)
        System.out.println(dict.search("...."));  // false (no 4-letter words)
    }
}

Output:
false
true
true
true
true
false

Application 3: Longest Common Prefix

Find the longest string that is a prefix of all input strings.

["flower","flow","flight"] → "fl"
["dog","racecar","car"]    → ""
["interview","interact","internal"] → "inter"

TRIE APPROACH:
  Insert all words.
  Walk from root: continue only when node has EXACTLY ONE child
                  AND isEndOfWord = false.
  Stop at any branch or word endpoint.

["flower","flow","flight"]:
  f: root has only child 'f' → continue, prefix="f"
  l: f has only child 'l' → continue, prefix="fl"
  Branch at 'l': children 'o' (flower,flow) and 'i' (flight) → STOP

  Longest common prefix = "fl" ✓

Java

public class LongestCommonPrefix {

    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
        int passCount = 0;   // How many words pass through this node
    }

    public static String longestCommonPrefix(String[] words) {
        if (words == null || words.length == 0) return "";

        // Build trie
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode curr = root;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (curr.children[i] == null) curr.children[i] = new TrieNode();
                curr = curr.children[i];
                curr.passCount++;
            }
            curr.isEnd = true;
        }

        // Walk root until branch or end
        StringBuilder prefix = new StringBuilder();
        TrieNode curr = root;
        int n = words.length;

        while (true) {
            TrieNode next = null;
            int childCount = 0;

            for (TrieNode child : curr.children) {
                if (child != null && child.passCount == n) {
                    next = child;
                    childCount++;
                }
            }

            // Stop if more than one path continues OR no path continues OR word ends here
            if (childCount != 1 || curr.isEnd) break;

            // Find which letter leads to next
            for (int i = 0; i < 26; i++) {
                if (curr.children[i] == next) {
                    prefix.append((char)('a' + i));
                    break;
                }
            }
            curr = next;
        }

        return prefix.toString();
    }

    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(
            new String[]{"flower","flow","flight"}));      // fl
        System.out.println(longestCommonPrefix(
            new String[]{"dog","racecar","car"}));          // (empty)
        System.out.println(longestCommonPrefix(
            new String[]{"interview","interact","internal"})); // inter
    }
}

Output:
fl
(empty string)
inter

Trie vs HashMap vs Sorted Array

OPERATION              HashMap<String,_>  Sorted Array   Trie
──────────────────────────────────────────────────────────────────
Exact search           O(L) average       O(L log n)     O(L)
Insert                 O(L) average       O(L + n)       O(L)
Delete                 O(L) average       O(L + n)       O(L)
Prefix exists?         O(L × n) worst     O(L log n)     O(L)
All words with prefix  O(L × n) worst     O(L log n + k) O(L + k)
Autocomplete           O(L × n)           O(L log n + k) O(L + k)
Sorted iteration       O(n log n)         O(n)           O(n)
Space                  O(n × L)           O(n × L)       O(n × L) worst
                                                         Better w/ shared prefixes

k = number of matching words, n = number of stored words, L = query length

WHEN TO USE TRIE:
  ✓ Many prefix-based queries
  ✓ Autocomplete / type-ahead
  ✓ Finding all words with a given prefix
  ✓ Longest common prefix
  ✓ Wildcard matching
  ✓ Word break / word search problems

WHEN TO USE HASHMAP:
  ✓ Only exact lookups needed (no prefix queries)
  ✓ Simpler implementation needed
  ✓ Dynamic word set with no prefix queries

Complexity Summary

Operation	Time	Space	Notes
Insert word	O(L)	O(L) new nodes	L = word length
Search exact	O(L)	O(1)	Follow path + check isEnd
Starts with	O(L)	O(1)	Follow path only
Delete word	O(L)	O(1)	Unmark isEnd + clean orphan nodes
Autocomplete	O(L + k)	O(k)	k = matching words × avg length
Wildcard search	O(26^w × L)	O(L)	w = wildcard count in pattern
Build trie (n words)	O(n × L)	O(n × L)	L = average word length
Longest common prefix	O(n × L)	O(n × L)	Build trie then walk

Common Mistakes

Forgetting to mark isEndOfWord on insert. Without this flag, search("cat") returns false even after inserting "cat" — the path exists but no word is marked as complete. Every insert must set isEndOfWord = true on the final node.

Confusing search and startsWith. search("ca") returns false for a trie containing "cat" — "ca" itself is not stored as a word. startsWith("ca") returns true because the path c→a exists. The difference is whether you check isEndOfWord at the end.

Wildcard: returning true as soon as one child exists instead of recursing into all. At a '.', you must recurse into every non-null child and return true only if at least one subtree matches. Short-circuiting after checking one child misses valid matches in other children.

Deleting a word that is a prefix of another. Deleting "car" when "card" is also stored must only unset isEndOfWord at the 'r' node — it must NOT delete the 'r' node itself (the path to 'card' still needs it). Always check whether a node has children before physically removing it.

Using char - 'a' on uppercase or non-letter characters. The fixed array[26] approach only handles lowercase a-z. For uppercase, digits, or Unicode, switch to a HashMap<Character, TrieNode> for the children.

Interview Questions

Q: What makes a Trie more efficient than a HashMap for prefix queries?

A HashMap can check if an exact key exists in O(L), but to find all words with a given prefix you must scan all n stored keys — O(n × L). A Trie stores characters as tree edges: navigating the prefix takes O(L), and all words with that prefix live in a subtree rooted at the prefix node. Collecting them takes O(k) where k is the count of matching words. For large word sets with many prefix queries, the Trie reduces prefix queries from O(n × L) to O(L + k).

Q: How does wildcard search in a Trie differ from exact search?

Exact search follows a single predetermined path — one node per character, O(L). Wildcard search with '.' must explore all 26 possible paths at each wildcard position — it's a DFS where '.' causes branching. The worst case is O(26^w × L) where w is the number of wildcards. In practice, most branches fail early, making it faster than the worst case. The key implementation change: at '.', loop over all non-null children and recurse into each.

Q: When should you use a HashMap for children instead of an array[26]?

Use array[26] when the character set is lowercase a-z only — it gives O(1) access with a simple index formula and is standard for interview implementations. Use HashMap when: (1) the character set is larger (uppercase + lowercase + digits + special = 62+ characters); (2) the trie is sparse and memory is critical (HashMap only allocates space for actual children); (3) the input can contain Unicode. In competitive programming and interviews, array[26] is almost always sufficient and simpler.

Summary

A Trie is a tree where each edge represents one character. A path from root to a node spells a prefix; nodes marked isEndOfWord spell complete stored words.

Three core operations — all O(L):

›Insert — follow or create one node per character; mark isEndOfWord at the last node
›Search — follow the path; return node != null && node.isEndOfWord
›startsWith — follow the path; return node != null (no isEndOfWord check)

Node structure: array[26] for lowercase a-z (constant space, O(1) access); HashMap for larger alphabets.

Four classic applications:

›Autocomplete — navigate to prefix node, DFS subtree collecting all words
›Wildcard search — at '.', recurse into all non-null children
›Longest common prefix — walk root until a branch or word endpoint
›Word break / word search — use trie to check prefixes during DFS

When Trie wins: any query involving prefixes — autocomplete, type-ahead, all-words-with-prefix, longest-common-prefix. O(L + k) vs O(n × L) for HashMap.

In the next topic you will explore Segment Tree — the range query data structure supporting O(log n) range sum, range minimum, and point updates.

Suggested Quiz

What is the time complexity of inserting a word of length L into a Trie?

1/6