Algorithm Guidecomplexity: O(m) (string length)

Trie

A prefix tree that stores strings letter by letter along its branches. By sharing common prefixes, it handles autocomplete, dictionaries, and prefix search in O(m) where m is the string length.

01Trie

Explore How It Works

Start a trie. Store strings letter by letter along the branches, and shared prefixes share the same path.

insert('cat') · build a new path c → a → t from the root, marking the final t as a 'word end'.

insert('car') · c·a already exist and are shared, so only r is added — sharing the prefix is the key idea.

insert('dog') · the very first letter differs, so build a completely new branch d → o → g.

search('car') · follow the letters c → a → r from the root, and since r is a 'word end', it's found.

Sharing common prefixes saves memory, and a lookup finishes in O(m), the word length. This is the basis of autocomplete.

Live Python

1class TrieNode:

2 def __init__(self):

3 self.children = {}

4 self.is_end = False

6class Trie:

7 def __init__(self):

8 self.root = TrieNode()

9 def insert(self, word):

10 node = self.root

11 for ch in word:

12 node = node.children.setdefault(ch, TrieNode())

13 node.is_end = True

14 def search(self, word):

15 node = self.root

16 for ch in word:

17 if ch not in node.children:

18 return False

19 node = node.children[ch]

20 return node.is_end

1 / 6

02 Understand It Simply

For Everyone

🔑How It Works

Characters form the edges, so words sharing a prefix share a path. Lookup time depends on the word's length, not on the size of the dictionary.

💡In Plain Words

A tree that stores strings letter by letter, sharing common prefixes.

It finds a word in O(m) and quickly gathers all words starting with a given prefix.

📍Where It's Used

–Search autocomplete
–dictionaries and spell-check
–IP routing

03 Python Implementation

A clean, readable reference implementation of the core logic of Trie.

core_implementation.py

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

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        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

04 Frequently Asked Questions

FAQ

What is Trie?+

A prefix tree that stores strings letter by letter along its branches. By sharing common prefixes, it handles autocomplete, dictionaries, and prefix search in O(m) where m is the string length.

What is the time complexity of Trie?+

The time complexity of Trie is O(m) (string length). Follow the step-by-step visualization to see exactly why.

Where is Trie used?+

Search autocomplete, dictionaries and spell-check, IP routing.

What's a simple analogy for Trie?+

Characters form the edges, so words sharing a prefix share a path. Lookup time depends on the word's length, not on the size of the dictionary.

→ Trees — see allRelated

Query/Update O(log n)