Trie (Prefix Tree)

DSA · Trees

Theory

A trie stores strings character by character, where each node represents a prefix and children are the possible next characters. Inserting or searching a word of length L takes O(L), independent of how many words are stored. A flag marks nodes where a complete word ends, and walking to a prefix node lets you list every word that starts with it.

Why we use it

Tries make prefix searches and autocomplete very fast and share storage between words with common prefixes.

When to use it

Use a trie for autocomplete, spell checking, dictionary lookups, IP routing tables and word-search puzzles.

How it works

  1. Start at root
  2. For each character of the word
  3. Child for this char exists? Yes: Move to it. No: Create child, move to it.
  4. Mark last node as end-of-word
  5. Prefix search follows the same path

Syntax

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

insert(word): walk/create nodes for each char; mark end
starts_with(prefix): walk the prefix; collect words below

Time: O(L) per word   Space: O(total characters)

Example

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    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.end = True
    def suggest(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        out = []
        def collect(n, path):
            if n.end:
                out.append(path)
            for ch in sorted(n.children):
                collect(n.children[ch], path + ch)
        collect(node, prefix)
        return out

t = Trie()
for w in ["sql", "snowflake", "spark", "sigma", "python", "pyspark"]:
    t.insert(w)
print("Suggestions for 's':", t.suggest("s"))
print("Suggestions for 'py':", t.suggest("py"))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic