AlgoPlus//structures / trie
Read the theory

Trie · Prefix Tree

Each edge is a letter; shared prefixes share a path.

Stability
—
In-Place
—
Space Complexity
—
Avg Time
—
Legend
Current node
Path / end of word
Node
AI Tutor Workspace
—
In a nutshell
A trie (also called a prefix tree) stores words as paths of letters branching out from a single root: follow the edges t-r-e-e and you have spelled "tree". Words that begin the same way share the same early path, so a whole dictionary folds into one compact tree. Looking up or adding a word costs only as many steps as the word is long — not how many words are stored — which is what makes tries ideal for autocomplete and spell-check.
Ready
Press play to begin the cinematic walkthrough.
A prefix tree: each edge is a character, so words sharing a prefix share a path. Lookups cost the length of the word, not the size of the dictionary.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Trie · Prefix Tree.
Code Simulator
▼
1
def bst(root, val):
2
    # insert / search / traverse
3
    if root is None:
4
        return Node(val)  # Inserted/Found
5
    if val < root.val:
6
        root.left = bst(root.left, val)
7
    else:
8
        root.right = bst(root.right, val)
9
    # traversal order
10
    visit(root.val)  # Visit
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.