DSA Tries

A Trie (pronounced "try," from the word "retrieval") is a specialized tree-like data structure used to store strings or sequences. Unlike a regular binary tree, each node in a trie represents a single character, and strings are formed by following paths from the root to a leaf.

Tries are exceptionally fast for operations involving strings — especially prefix-based searching — making them the data structure behind features like autocomplete, spell checkers, and IP routing tables.

How a Trie Works

Consider inserting the words "cat", "car", and "cart" into a trie:


# Trie structure after inserting "cat", "car", "cart":
#
# root
#  └── c
#       └── a
#            ├── t  (end of "cat")
#            └── r  (end of "car")
#                 └── t  (end of "cart")
#
# The prefix "ca" is shared by all three words — no duplication

Shared prefixes are stored only once, making a trie memory-efficient for large vocabularies with common prefixes.

Implementing a Trie in Python

Step 1: Define the TrieNode


class TrieNode:
    def __init__(self):
        self.children = {}       # Dictionary: character -> TrieNode
        self.is_end_of_word = False   # True if this node ends a complete word

Step 2: Define the Trie Class with Insert


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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()   # Create new node if missing
            node = node.children[char]             # Move to the next node
        node.is_end_of_word = True                 # Mark end of word

trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")
trie.insert("card")
trie.insert("dog")

Step 3: Search for a Word — O(m), where m = word length


    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False   # Character not found — word doesn't exist
            node = node.children[char]
        return node.is_end_of_word   # True only if this is a complete word

print(trie.search("car"))    # Output: True
print(trie.search("ca"))     # Output: False (not a complete word)
print(trie.search("dog"))    # Output: True
print(trie.search("dot"))    # Output: False

Step 4: Check if a Prefix Exists — O(m)


    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   # All prefix characters found

print(trie.starts_with("ca"))    # Output: True
print(trie.starts_with("do"))    # Output: True
print(trie.starts_with("xyz"))   # Output: False

Complete Trie with All Operations


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

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

    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_of_word = True

    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_of_word

    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

# Build and query the trie
t = Trie()
for word in ["apple", "app", "application", "apt", "bat", "ball"]:
    t.insert(word)

print(t.search("app"))          # True
print(t.search("apply"))        # False
print(t.starts_with("app"))     # True
print(t.starts_with("ba"))      # True
print(t.starts_with("xyz"))     # False

Autocomplete Feature Using a Trie

Finding all words with a given prefix is one of the most common real-world uses of a trie.


def autocomplete(trie, prefix):
    node = trie.root
    for char in prefix:
        if char not in node.children:
            return []   # Prefix not found
        node = node.children[char]

    results = []
    # DFS from the node reached by the prefix
    def dfs(current_node, current_word):
        if current_node.is_end_of_word:
            results.append(current_word)
        for char, child in current_node.children.items():
            dfs(child, current_word + char)

    dfs(node, prefix)
    return results

t = Trie()
for word in ["apple", "app", "application", "apt", "apt", "bat", "ball", "banana"]:
    t.insert(word)

print(autocomplete(t, "app"))    # Output: ['app', 'apple', 'application']
print(autocomplete(t, "ba"))     # Output: ['bat', 'ball', 'banana']

Deleting a Word from a Trie


def delete(root, word, depth=0):
    if root is None:
        return None

    if depth == len(word):
        if root.is_end_of_word:
            root.is_end_of_word = False
        if not root.children:
            return None   # Node can be deleted
        return root

    char = word[depth]
    if char in root.children:
        root.children[char] = delete(root.children[char], word, depth + 1)
        if root.children[char] is None:
            del root.children[char]

    return root

Tries vs Hash Maps for Strings

  • Prefix search: Tries are O(m); hash maps require full string matching for every entry — O(n × m).
  • Sorted iteration: Tries support lexicographic traversal naturally; hash maps do not maintain order.
  • Memory: Tries use more memory per character; hash maps use less with no prefix sharing benefit.
  • Exact lookup: Hash maps are faster for exact key lookup — O(1).

Big O Summary for Trie Operations

  • Insert — O(m), where m is the length of the word
  • Search — O(m)
  • Prefix check (starts_with) — O(m)
  • Autocomplete (all words with prefix) — O(m + k), where k is total characters in results
  • Space — O(n × m) where n is the number of words

Key Points

  • A trie stores strings by sharing common prefixes across nodes, one character per node.
  • Each node holds a dictionary of children and a flag indicating whether it marks the end of a word.
  • Insert, search, and prefix check all run in O(m) time — proportional to the word length, not the dictionary size.
  • Tries are ideal for autocomplete, spell checking, IP routing, and dictionary applications.
  • Unlike hash maps, tries support prefix-based operations natively and efficiently.
  • The DFS technique is used to collect all words sharing a given prefix for autocomplete features.
Previous lessons
Back to courses
Next lessons

Leave a Comment