DSA Notes

Hub Algorithm vs Data Structure - Key Differences Real-World Applications of DSA Time and Space Complexity Overview What is DSA? Data Structures and Algorithms Why Learn Data Structures and Algorithms Asymptotic Analysis - Understanding Algorithm Growth Best, Average, and Worst Case Analysis Big O Notation - Upper Bound Analysis Big Omega Notation - Lower Bound Analysis Big Theta Notation - Tight Bound Analysis Space Complexity - Memory Analysis Time Complexity Examples and Analysis Array Interview Problems and Solutions Array Operations - Insert, Delete, Search Array Rotation Techniques Array Searching Techniques Arrays - Fundamental Data Structure Dynamic Arrays - Flexible Sizing Multidimensional Arrays - 2D and Beyond Sliding Window Technique for Arrays Anagram Problems - Character Rearrangement Palindrome Problems and Solutions Pattern Searching in Strings String Interview Problems Collection String Matching Algorithms - Pattern Searching String Operations - Concatenation, Substring, Manipulation String Data Structure - Fundamentals Circular Linked List - Ring Structure Doubly Linked List - Bidirectional Traversal Linked List Interview Problems Linked List - Data Structure Fundamentals Linked List Operations - Insert, Delete, Reverse Reverse Linked List - Iterative and Recursive Singly Linked List - Implementation and Operations Balanced Parentheses - Stack Application Infix, Prefix, Postfix Expressions - Stack Application Stack Implementation Techniques Stack Interview Problems and Solutions Stack Data Structure - LIFO Principle Stack using Arrays - Static Implementation Stack using Linked Lists - Dynamic Implementation Circular Queue - Efficient Space Usage Deque (Double Ended Queue)Priority Queue - Custom Ordering Queue Applications - Real-World Use Cases Queue Implementation - Array and Linked List Queue Interview Problems and Solutions Queue Data Structure - FIFO Principle AVL Tree - Self-Balancing Binary Search Tree Binary Search Tree (BST)Binary Tree - Structure and Operations Fenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BST Segment Tree - Range Query Data Structure Tree Interview Problems Collection Tree Data Structure Fundamentals Tree Traversals - Inorder, Preorder, Postorder, Level Order Heap Data Structure Heap Operations Heap Interview Problems Max-Heap Min-Heap Implementation and Use Cases Priority Queue using Heap Bellman-Ford Algorithm Breadth-First Search (BFS) Algorithm Depth-First Search (DFS) Algorithm Dijkstra\Floyd-Warshall Algorithm Graph Interview Problems Graph Data Structure Fundamentals Graph Representation Methods Kruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete Comparison Topological Sorting Union-Find (Disjoint Set Union)Separate Chaining Collision Handling Hash Functions Hashing Fundamentals Hashing Interview Problems Open Addressing Bubble Sort - Simple Sorting Algorithm Counting Sort - Non-Comparison Sorting Heap Sort - Heap Based Sorting Insertion Sort - Build Sorted Array Merge Sort - Divide and Conquer Quick Sort - Partition Based Sorting Radix Sort - Digit Based Sorting Selection Sort - Selection Based Sorting Sorting Algorithms Comparison - Choosing the Right Algorithm Sorting Algorithms - Fundamentals and Concepts Binary Search - Efficient Searching Interpolation Search - Intelligent Searching Linear Search - Sequential Search Algorithm Search Algorithms Comparison Searching Algorithm Interview Problems Ternary Search Algorithm Backtracking with Recursion Recursion Fundamentals - Base Case and Recurrence Recursion Problems and Solutions Recursion Tree - Visualizing Function Calls Recursion vs Iteration - Comparing Approaches Tail Recursion - Optimization Technique Dynamic Programming Interview Problems Dynamic Programming Fundamentals Fibonacci with Dynamic Programming 0/1 Knapsack Problem Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain Multiplication Memoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection Problem Fractional Knapsack Greedy Interview Problems Greedy Algorithm Fundamentals Huffman Coding — Data Structures & Algorithms Job Sequencing with Deadlines Backtracking Fundamentals Backtracking Practice Problems N-Queens Problem Rat in a Maze Subset Generation Sudoku Solver Codeforces Guide for Competitive Programmers Common Competitive Programming Techniques Contest Strategies for Competitive Programming Competitive Programming Introduction Fast Input/Output for Competitive Programming LeetCode Guide for Interview Preparation Bit Manipulation - Advanced Techniques Bloom Filter - Probabilistic Data Structure Computational Geometry - Algorithms and Techniques Disjoint Set Union (DSU) - Union Find Randomized Algorithms - Probabilistic Computing Skip List - Probabilistic Balanced Structure Suffix Array - String Indexing Trie - Prefix Tree for Efficient Searching Autocomplete System Using Trie Library Management System Using DSA Route Finder Using Graphs Mini Search Engine Project Social Network Analysis Using Graphs Essential Coding Patterns for Interviews DSA Cheatsheet: Quick Reference Essential DSA Interview Questions FAANG DSA Sheet: Company-Specific Patterns and Problems Problem Solving Strategies for Coding Interviews Complexity Cheatsheet Important Algorithms Summary Best Practice Platforms for DSA Recommended Books for DSA

Trie - Prefix Tree for Efficient Searching

Master trie data structures for autocomplete and prefix-based searching.

What is a Trie?

A Trie (pronounced "try") is a tree-like data structure designed specifically for storing and searching strings efficiently. Unlike a binary search tree that stores complete keys in each node, a trie stores one character per node, with the path from root to any node representing a prefix of the stored strings.

The name comes from "retrieval" — because tries make string retrieval extremely fast. If you have ever used autocomplete on Google, phone keyboards, or IDE code completion, you have used functionality powered by trie-like structures.

Key insight: A trie lets you search for any word in O(m) time where m is the word length — completely independent of how many words are stored. Whether your dictionary has 100 words or 10 million words, looking up a 5-letter word always takes exactly 5 steps.

Implementation in Python

Example

class TrieNode: def __init__(self): self.children = {} # char -> TrieNode self.is_end_of_word = False self.word_count = 0 # How many words pass through this node class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): """Insert a word into the trie. O(m) where m = len(word)""" node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.word_count += 1 node.is_end_of_word = True def search(self, word): """Check if exact word exists. O(m)""" node = self._find_node(word) return node is not None and node.is_end_of_word def starts_with(self, prefix): """Check if any word starts with given prefix. O(m)""" return self._find_node(prefix) is not None def count_with_prefix(self, prefix): """Count words starting with prefix. O(m)""" node = self._find_node(prefix) return node.word_count if node else 0 def _find_node(self, prefix): """Navigate to the node representing prefix""" node = self.root for char in prefix: if char not in node.children: return None node = node.children[char] return node def delete(self, word): """Delete a word from the trie. O(m)""" self._delete_helper(self.root, word, 0) def _delete_helper(self, node, word, depth): if depth == len(word): if node.is_end_of_word: node.is_end_of_word = False return len(node.children) == 0 return False char = word[depth] if char not in node.children: return False should_delete = self._delete_helper(node.children[char], word, depth + 1) if should_delete: del node.children[char] return not node.is_end_of_word and len(node.children) == 0 return False def autocomplete(self, prefix, limit=10): """Find all words starting with prefix. O(m + k) where k = results""" node = self._find_node(prefix) if not node: return [] results = [] self._collect_words(node, prefix, results, limit) return results def _collect_words(self, node, current_word, results, limit): if len(results) >= limit: return if node.is_end_of_word: results.append(current_word) for char in sorted(node.children.keys()): self._collect_words(node.children[char], current_word + char, results, limit) # Usage trie = Trie() words = ["apple", "app", "application", "apply", "banana", "band", "bandana"] for word in words: trie.insert(word) print(trie.search("app")) # True print(trie.search("ap")) # False (not a complete word) print(trie.starts_with("app")) # True print(trie.count_with_prefix("app")) # 4 (apple, app, application, apply) print(trie.autocomplete("app")) # ['app', 'apple', 'application', 'apply'] print(trie.autocomplete("ban")) # ['banana', 'band', 'bandana']

Java Implementation

Example

class Trie { private TrieNode root; class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord = false; } public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) node.children[idx] = new TrieNode(); node = node.children[idx]; } node.isEndOfWord = true; } public boolean search(String word) { TrieNode node = findNode(word); return node != null && node.isEndOfWord; } public boolean startsWith(String prefix) { return findNode(prefix) != null; } private TrieNode findNode(String s) { TrieNode node = root; for (char c : s.toCharArray()) { int idx = c - 'a'; if (node.children[idx] == null) return null; node = node.children[idx]; } return node; } }

Complexity Analysis

Operation	Time	Space
Insert	O(m)	O(m) per word worst case
Search	O(m)	O(1)
Prefix search	O(m)	O(1)
Delete	O(m)	O(1)
Autocomplete	O(m + k)	O(k) for results
Total space	-	O(n × m × alphabet_size) worst case

Where m = word length, n = number of words, k = number of matches.

Trie vs Other Data Structures

Feature	Trie	HashMap	BST
Exact search	O(m)	O(m) avg	O(m log n)
Prefix search	O(m)	O(n×m)	O(m log n)
Autocomplete	O(m + k)	O(n×m)	O(m log n + k)
Sorted iteration	Natural	Not possible	Natural
Space	Can be large	Compact	Moderate
Best for	Prefix operations	Exact lookups	Ordered data

Real-World Applications

Autocomplete systems — Google search, IDE code completion, phone keyboards
Spell checkers — finding close matches for misspelled words
IP routing — longest prefix matching in router tables
Phone directories — T9 predictive text, contact search
Genome analysis — searching for DNA/RNA sequence patterns
Word games — Scrabble solvers, Boggle finders, crossword helpers

Variations

Compressed Trie (Patricia/Radix Tree): Merges chains of single-child nodes into one edge. Reduces space significantly for sparse datasets.

Ternary Search Tree: Each node has three children (less than, equal to, greater than). Uses less space than standard tries while maintaining good performance.

Suffix Trie/Tree: Stores all suffixes of a string. Used for advanced string matching problems.

Interview Questions

Q1: What is the time complexity of searching in a trie vs a hash map? A: Both are O(m) for exact search where m is key length. But tries excel at prefix operations — finding all words with a given prefix is O(m + k) vs O(n×m) for hash maps scanning all entries.

Q2: How would you implement autocomplete using a trie? A: Navigate to the node representing the prefix (O(m)). Then perform DFS/BFS from that node to collect all complete words below it. Optionally sort by frequency or recency for better suggestions.

Q3: How do you handle memory issues with tries? A: Use compressed tries (merge single-child chains), use arrays only for the alphabet subset actually used, or use hash maps instead of arrays for children (trading some speed for space).

Q4: What is the difference between a trie and a suffix tree? A: A regular trie stores a set of words. A suffix tree stores all suffixes of a single string, enabling substring matching in O(m) time. Suffix trees are specialized for within-string pattern matching.

Q5: How would you find the longest common prefix of all words in a trie? A: Start from root, follow the path as long as each node has exactly one child and is not end-of-word. The path length is the longest common prefix. Time: O(m) where m is the LCP length.

Key Takeaways

Tries provide O(m) operations independent of dataset size — perfect for dictionaries and autocomplete
The prefix-sharing property makes tries memory-efficient for words with common prefixes
Every coding interview involving string prefixes likely needs a trie
In practice, compressed tries and ternary search trees offer better space-time trade-offs
Learn the basic insert/search/startsWith operations — they appear directly in LeetCode problems

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Trie - Prefix Tree for Efficient Searching.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, trie

Related Data Structures & Algorithms Topics

Continue learning this concept

Advanced TopicsBit Manipulation - Advanced TechniquesMaster bit manipulation techniques, bitwise operations, bit masking, and advanced binary algorithms for competitive programming and interviews.Advanced TopicsBloom Filter - Probabilistic Data StructureLearn about Bloom filters, a space-efficient probabilistic data structure for set membership testing with constant-time operations.Advanced TopicsComputational Geometry - Algorithms and TechniquesMaster computational geometry concepts, geometric algorithms, and problem-solving techniques.Advanced TopicsDisjoint Set Union (DSU) - Union FindMaster DSU with path compression and union by rank for efficient operations.Advanced TopicsRandomized Algorithms - Probabilistic ComputingExplore randomized algorithms and probabilistic approaches.Advanced TopicsSkip List - Probabilistic Balanced StructureLearn skip lists as probabilistic alternative to balanced trees.

PreviousSuffix Array - String Indexing NextAutocomplete System Using Trie

DSA Notes

Trie - Prefix Tree for Efficient Searching

Master trie data structures for autocomplete and prefix-based searching.

What is a Trie?

Implementation in Python

Example

Java Implementation

Example

Complexity Analysis

Operation	Time	Space
Insert	O(m)	O(m) per word worst case
Search	O(m)	O(1)
Prefix search	O(m)	O(1)
Delete	O(m)	O(1)
Autocomplete	O(m + k)	O(k) for results
Total space	-	O(n × m × alphabet_size) worst case

Where m = word length, n = number of words, k = number of matches.

Trie vs Other Data Structures

Feature	Trie	HashMap	BST
Exact search	O(m)	O(m) avg	O(m log n)
Prefix search	O(m)	O(n×m)	O(m log n)
Autocomplete	O(m + k)	O(n×m)	O(m log n + k)
Sorted iteration	Natural	Not possible	Natural
Space	Can be large	Compact	Moderate
Best for	Prefix operations	Exact lookups	Ordered data

Real-World Applications

Autocomplete systems — Google search, IDE code completion, phone keyboards
Spell checkers — finding close matches for misspelled words
IP routing — longest prefix matching in router tables
Phone directories — T9 predictive text, contact search
Genome analysis — searching for DNA/RNA sequence patterns
Word games — Scrabble solvers, Boggle finders, crossword helpers

Variations

Compressed Trie (Patricia/Radix Tree): Merges chains of single-child nodes into one edge. Reduces space significantly for sparse datasets.

Ternary Search Tree: Each node has three children (less than, equal to, greater than). Uses less space than standard tries while maintaining good performance.

Suffix Trie/Tree: Stores all suffixes of a string. Used for advanced string matching problems.

Interview Questions

Key Takeaways

Tries provide O(m) operations independent of dataset size — perfect for dictionaries and autocomplete
The prefix-sharing property makes tries memory-efficient for words with common prefixes
Every coding interview involving string prefixes likely needs a trie
In practice, compressed tries and ternary search trees offer better space-time trade-offs
Learn the basic insert/search/startsWith operations — they appear directly in LeetCode problems

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Trie - Prefix Tree for Efficient Searching.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.

Search Terms

data-structures-algorithms, data structures & algorithms, data, structures, algorithms, advanced, topics, trie

Related Data Structures & Algorithms Topics

Continue learning this concept

PreviousSuffix Array - String Indexing NextAutocomplete System Using Trie