DSA — Non-Linear DS

Trie (Prefix Tree)

Tree where each node represents a character. Root to leaf spells a word. O(m) search where m = word length — used in autocomplete, spell check, and routing.

— min read
O(m)Search
O(m)Insert
PrefixMatching
AutoComplete
✓NLP / DNS
// TRIE (PREFIX TREE)
Interactive visualization
How It Works
Python Code
Complexity
Quiz
Practice
01
Insert Word
Walk character by character, create nodes as needed.
for char in word: node = node.children[char]
02
Search
Follow chars from root; fail if any char missing.
if char not in node.children: return False
03
Prefix Match
Trie naturally supports prefix queries — stop early.
04
Use Cases
Autocomplete, spell check, IP routing, word games.
python 
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end
O(m)
Insert
m = length of word
O(m)
Search
m = length of word
O(n×m)
Space
n words, avg length m
Autocomplete
Key Use
All words with given prefix — fast!
What is the time complexity to search a word of length m in a Trie?
Progress 0 / 2 solved
2 problems · 2 PBC · 0 Startup
#026 Longest Common Prefix Google PBC →
#122 Word Break Meta, Amazon PBC →
← Heap