DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master the Trie (prefix tree) data structure — what it is, how it stores strings in a tree of characters, complete implementation with insert/search/delete/startsWith, compressed tries, applications in autocomplete and spell checking, and classic interview problems.
What Is a Trie?
A Trie (pronounced "try", from retrieval) is a tree-shaped data structure specifically designed for storing and searching strings. Unlike a Binary Search Tree that stores complete values at nodes, a Trie stores strings character by character — each edge represents one character, and a path from root to any node spells out a prefix.
The core idea: Instead of hashing an entire string to store it, a Trie breaks the string into individual characters and builds a tree where shared prefixes share tree branches.
Example
Storing words: "cat", "car", "card", "care", "bat"
root
/ \
c b
| |
a a
/ \ |
t r t*
* / \
d* e*
* = marks end of a valid word
Every path from root to a * node spells a complete word. The prefix "ca" is shared by "cat", "car", "card", and "care" — stored once, not four times.
Node Structure
python example
class TrieNode:
"""
Each node represents one character position.
children: dict mapping character → next TrieNode
is_end: True if this node marks the end of a complete word
"""
def __init__(self):
self.children = {} # char → TrieNode
self.is_end = False # True if a word ends here
self.word = None # Optional: store the complete word at end nodesFor a fixed alphabet (26 lowercase letters), use an array instead of dict for better cache performance:
Example
class TrieNodeArray:
def __init__(self):
self.children = [None] * 26 # One slot per lowercase letter
self.is_end = False
Complete Trie Implementation
Example
class Trie:
"""
Trie (prefix tree) implementation.
Supports: insert, search, startsWith, delete, all_words_with_prefix.
"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Insert word into trie.
Time: O(m) where m = len(word)
Space: O(m) in worst case (brand new prefix)
"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode() # Create new node if needed
node = node.children[char] # Move down
node.is_end = True # Mark end of word
node.word = word # Store the complete word
def search(self, word: str) -> bool:
"""
Return True if word exists in trie (exact match).
Time: O(m)
"""
node = self._find_node(word)
return node is not None and node.is_end
def starts_with(self, prefix: str) -> bool:
"""
Return True if any word in trie starts with prefix.
Time: O(m) where m = len(prefix)
"""
return self._find_node(prefix) is not None
def _find_node(self, prefix: str):
"""Navigate to the node at end of prefix. Returns None if not found."""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
def get_all_words_with_prefix(self, prefix: str) -> list:
"""
Return all words that start with prefix.
Time: O(m + k) where k = total chars in results
"""
node = self._find_node(prefix)
if node is None:
return []
results = []
self._dfs(node, results)
return results
def _dfs(self, node: TrieNode, results: list) -> None:
"""DFS to collect all words in subtree."""
if node.is_end:
results.append(node.word)
for child in node.children.values():
self._dfs(child, results)
def delete(self, word: str) -> bool:
"""
Delete word from trie.
Returns True if word was found and deleted.
Time: O(m)
Strategy: recursively remove nodes that become unnecessary.
"""
return self._delete(self.root, word, 0)
def _delete(self, node: TrieNode, word: str, depth: int) -> bool:
"""Recursive delete helper. Returns True if current node should be deleted."""
if depth == len(word):
if not node.is_end:
return False # Word not in trie
node.is_end = False
node.word = None
return len(node.children) == 0 # Delete if no children
char = word[depth]
if char not in node.children:
return False # Word not in trie
should_delete_child = self._delete(node.children[char], word, depth + 1)
if should_delete_child:
del node.children[char]
return not node.is_end and len(node.children) == 0
return False
Step-by-Step Trace
| root | c → a → t* |
| root | c → a → t* |
| └ | r* |
| root | c → a → t* |
| └ | r* → d* |
| search("car") | Navigate c→a→r, is_end=True → True |
| search("ca") | Navigate c→a, is_end=False → False |
| starts_with("ca") | Navigate c→a, node exists → True |
| starts_with("dog") | d not in root.children → False |
Autocomplete Implementation
Example
class AutocompleteSystem:
"""
Autocomplete using Trie: O(m) to get all suggestions.
"""
def __init__(self, words: list):
self.trie = Trie()
for word in words:
self.trie.insert(word)
def get_suggestions(self, prefix: str, limit: int = 5) -> list:
"""Return up to 'limit' words starting with prefix."""
all_words = self.trie.get_all_words_with_prefix(prefix)
return sorted(all_words)[:limit] # Sort alphabetically, take first k
dictionary = ["apple", "app", "application", "apply", "apt", "banana", "band"]
ac = AutocompleteSystem(dictionary)
print(ac.get_suggestions("app")) # ['app', 'apple', 'application', 'apply']
print(ac.get_suggestions("ban")) # ['banana', 'band']
print(ac.get_suggestions("xyz")) # []
Spell Checker with Trie
Example
class SpellChecker:
"""
Spell checker: find all words within edit distance 1.
"""
def __init__(self, words: list):
self.trie = Trie()
for word in words:
self.trie.insert(word)
self.words = set(words)
def is_correct(self, word: str) -> bool:
return self.trie.search(word)
def suggest(self, word: str) -> list:
"""Return words that differ by exactly one character."""
suggestions = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
candidate = word[:i] + c + word[i+1:]
if candidate != word and candidate in self.words:
suggestions.append(candidate)
return list(set(suggestions))
sc = SpellChecker(["the", "thee", "there", "their", "they"])
print(sc.is_correct("the")) # True
print(sc.is_correct("tge")) # False
print(sc.suggest("tge")) # ['the'] (differs at position 1)
Trie vs Hash Map
When Trie is BETTER than Hash Map
✅ Prefix search: "find all words starting with X"
✅ Alphabetical ordering: DFS gives sorted order free
✅ Longest prefix match (used in IP routing)
✅ Auto-complete and spell check
✅ Finding shortest unique prefix
When Hash Map is BETTER than Trie
✅ Exact key lookup: hash map is O(1), trie is O(m)
✅ Non-string keys: tries only work on string-like data
✅ Simpler implementation needed
✅ Memory-constrained: hash map uses less memory for sparse data
Interview Problems
Problem 1 — Word Search II (Find all words in board)
Example
def find_words(board, words):
"""
Find all words from the list that exist in the 2D character board.
Uses Trie for efficient multi-word search.
O(m × 4^L + total_chars) where L = max word length.
"""
trie = Trie()
for word in words:
trie.insert(word)
m, n = len(board), len(board[0])
found = set()
def dfs(r, c, node, path):
char = board[r][c]
if char not in node.children:
return
next_node = node.children[char]
if next_node.is_end:
found.add(next_node.word)
board[r][c] = '#' # Mark visited
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '#':
dfs(nr, nc, next_node, path + char)
board[r][c] = char # Restore
for r in range(m):
for c in range(n):
dfs(r, c, trie.root, "")
return list(found)
Problem 2 — Longest Word in Dictionary
Example
def longest_word(words):
"""
Find longest word where every prefix also exists in the dictionary.
"""
trie = Trie()
for word in words:
trie.insert(word)
result = ""
def dfs(node, current):
nonlocal result
if len(current) > len(result):
result = current
for char, child in sorted(node.children.items()):
if child.is_end: # Only continue if prefix is a valid word
dfs(child, current + char)
dfs(trie.root, "")
return result
print(longest_word(["a","banana","app","appl","ap","apply","apple"]))
# "apple" (a→ap→app→appl→apple, all prefixes exist)
Problem 3 — Shortest Unique Prefix for Every Word
Example
def shortest_unique_prefixes(words):
"""
For each word, find its shortest prefix that uniquely identifies it.
"""
trie = Trie()
# Augment trie: count how many words pass through each node
class CountNode:
def __init__(self):
self.children = {}
self.count = 0
self.is_end = False
root = CountNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = CountNode()
node = node.children[char]
node.count += 1
node.is_end = True
results = []
for word in words:
node = root
prefix = ""
for char in word:
prefix += char
node = node.children[char]
if node.count == 1: # Only one word uses this prefix
break
results.append(prefix)
return results
print(shortest_unique_prefixes(["zebra", "dog", "duck", "dove"]))
# ["z", "dog", "du", "dov"]
Complexity Summary
| Operation | Time | Space |
|---|---|---|
| Insert word of length m | O(m) | O(m) worst case |
| Search exact word | O(m) | O(1) |
| Search prefix | O(m) | O(1) |
| Get all words with prefix | O(m + total) | O(total) |
| Delete word | O(m) | O(1) |
| Build trie for n words | O(n × m_avg) | O(n × m_avg) |
Memory: A naive trie node with 26 child pointers uses 26 × 8 = 208 bytes per node. For sparse tries (few words with large alphabet), use a dictionary instead of array for children.
Summary
- A Trie stores strings character by character, sharing common prefixes
- Insert/Search: O(m) where m = word length — independent of dictionary size
- Prefix search: Trie's superpower — O(m) to find all words with a given prefix
- Applications: Autocomplete, spell checker, IP routing (longest prefix match), word search
- Trade-off: More memory than hash map for exact lookup; worth it when prefix operations are needed
*Next: Disjoint Set Union (DSU)*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Trie Data Structure — Complete Guide with Implementation and Applications.
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 — Complete Guide with All Tricks and Interview ProblemsMaster bit manipulation completely — bitwise operators with truth tables, bit shifting, common tricks for setting/clearing/toggling bits, XOR magic properties, counting set bits (Brian Kernighan), power of two checks, swap without temp variable, and 15 classic interview problems solved with bit manipulation.Advanced TopicsBloom Filter — Space-Efficient Probabilistic Membership TestingMaster Bloom filters — what they are, how multiple hash functions create a probabilistic set, false positive analysis and optimal parameter calculation, complete implementation, applications in databases and networking, and counting Bloom filters for deletion support.Advanced TopicsComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsMaster computational geometry fundamentals — cross product for orientation testing, point-in-polygon detection, convex hull algorithms (Graham scan and Jarvis march), closest pair of points, line segment intersection, and applications in graphics and competitive programming.Advanced TopicsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankMaster Disjoint Set Union (Union-Find) completely — what it is, naive implementation, path compression optimization, union by rank, combined O(α(n)) amortized complexity, KruskalAdvanced TopicsRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesMaster randomized algorithms — the difference between Las Vegas and Monte Carlo algorithms, randomized quicksort with expected O(n log n), reservoir sampling for streaming data, randomized selection for kth element, Miller-Rabin primality test, and why randomization defeats adversarial inputs.Advanced TopicsSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsMaster skip lists — what they are, how probabilistic layering achieves O(log n) expected search, complete implementation with insert/search/delete, why Redis and LevelDB use skip lists instead of balanced trees, and comparison with AVL trees and hash maps.