Build a trie

Lesson 13.2 · Medium · Insert words · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

Insert words into a trie, a tree where each step down is one letter. Words that start the same share a path.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

"a"apple0

app1

apply2

apt3

bat4

bath5

batch6

bar7

"a" has no branch here yet. Create a new node.

path a · nodes 1

1 / 40

The idea

Complexity

Time	Space	Why
`O(L) per word`	`O(total letters)`	L = word length; shared prefixes are stored once.

In Python

class Trie:
    def __init__(self): self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True                   # end of word

</> Now code it →Try it on LeetCode: Implement Trie (Prefix Tree) →

Summary: say it in the interview

Start at an empty root. For each letter, follow the existing branch or create one. Mark the last node as a word end. Words that share a prefix share nodes, so the trie stores that prefix once.
Time O(L) per word, space O(total letters). L = word length; shared prefixes are stored once.