AI Hints
Home›DSA in Python Tutorial›Tries and Tree Review
DSA in Python · Lesson 73 of 132

Tries

A tree of letters.

⏱ 2 min read▶ Video at 1:25:55🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

When you type CA on your phone, it suggests cat, car, and camera, instantly. That's powered by a trie. It's a tree where each step down is one letter, so words that share a beginning share a path.

Tries
From the video: Tries
  • Type 'ca', get suggestions
  • A tree of letters
  • Shared beginnings share a path

Building a trie

Each node is a dictionary, from a letter to the next node. Insert walks down the word letter by letter, creating nodes as needed. A dollar sign marks where a complete word ends. Here we insert car, cat, and cap, and print the root. Run it. All three words share the C and the A.

trie.pypython
class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True

t = Trie()
for w in ["car", "cat", "cap"]:
    t.insert(w)
print(t.root)
Output
{'c': {'a': {'r': {'$': True}, 't': {'$': True}, 'p': {'$': True}}}}

Trie costs

Inserting or finding a word takes O of L steps, where L is the length of the word. It doesn't matter if the trie holds ten words or ten million. That's why tries are used for autocomplete, spell checkers, and routing tables on the internet.

keyvalue
InsertO(length)
FindO(length)
Prefix searchO(prefix length)
Used inautocomplete, spell check

Summary

A trie stores words letter by letter, so shared beginnings share a path. Lookups take O of word length. Next, using a trie for autocomplete.

Key takeaways
  • One letter per step
  • $ marks a word
  • O(length)
Next up: Practice: Autocomplete — words with a prefix