DSA — Trie

What is a Trie?

A tree-like data structure for storing strings, where each node represents a character.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

Insert

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

Search

def search(self, word):
    node = self.root
    for char in word:
        if char not in node.children:
            return False
        node = node.children[char]
    return node.is_end

Starts With

def starts_with(self, prefix):
    node = self.root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True

Applications

Application	Description
Autocomplete	Word suggestions
Spell checking	Valid word lookup
IP routing	Longest prefix match
Word games	Scrabble, Boggle

Mini Practice

1. Implement a trie
2. Search for words
3. Find all words with prefix
4. Auto-complete feature

Up Next

Continue with Segment Tree — range query data structure.