learningto/pass

Tries

AdvancedData Structures

Tries (prefix trees) are the go-to structure for autocomplete, spell checking, and IP routing. Google uses them extensively in search. Master insertion, search, and prefix matching.

AVG TIME
O(m)
SPACE
O(n * m)
BEST
O(m)
WORST
O(m)

Key Concepts

  • 1m is the length of the word being inserted/searched
  • 2Each node stores children dict and is_end_of_word flag
  • 3Prefix search is O(m) - just traverse without requiring is_end
  • 4Can store additional data at terminal nodes (frequency, definition)
  • 5Compressed trie (radix tree) reduces space for sparse tries

In Python

Concept to Code- 2 structures for this topic
declare
seen = {}  # or seen = dict()
common ops
seen[key] = val
O(1)
key in seen
O(1)
seen.get(key, default)
O(1)
del seen[key]
O(1)
seen.keys()
O(n)
seen.items()
O(n)
say in interview
"I'll use a hash map for O(1) lookups"
In Python, dict preserves insertion order (since 3.7). In interviews, don't rely on this unless asked.

Math You Need For This

A phone tree. Press 1 for sales, then press 2 for existing customers, then press 3 for billing. Each keypress is one letter/step. The depth of the menu tree equals the longest phone path.

Required concepts
Key math ideas
1 / 2

Constant time - O(1)

No matter how large the input is, this operation always takes the same amount of time. The size of n simply does not matter.

Visual: A perfectly flat horizontal line on a graph. The line never rises no matter how far right you go.

Think of it this way: Looking up a word in a dictionary if you already know the exact page number. It does not matter how thick the dictionary is.

For algorithms: Accessing array[3] is O(1) because the computer calculates the memory address directly: start + 3 * item_size. One calculation, done.

Interactive 3D Visualization

Array
Access: O(1)Search: O(n)Space: O(n)
Drag to orbit - Scroll to zoom

Python Implementation

example.py
Loading...
Now try it yourself
1 challenge with test cases and AI feedback
Practice Now

Complexity Analysis

1481216n²nlog n1n (input size)
COMMON OPERATIONS
Array
Access:O(1)
Search:O(n)
Insert end:O(1)*
Insert mid:O(n)
Hash Map
Get/Set:O(1)*
Delete:O(1)*
Search value:O(n)
Iterate:O(n)
Linked List
Access:O(n)
Search:O(n)
Insert head:O(1)
Delete known:O(1)
Binary Search
Search:O(log n)
Insert:O(log n)
Balanced BST
Search:O(log n)
Insert:O(log n)
Delete:O(log n)
Heap
Peek min/max:O(1)
Push:O(log n)
Pop:O(log n)
Heapify:O(n)
Graph (BFS/DFS)
Traversal:O(V+E)
Dijkstra (heap):O((V+E) log V)
Merge / Quick Sort
Sort:O(n log n)
Space (merge):O(n)
Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Tries into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Sorting
Tries
Next: Sorting