Space Complexity of a Trie
Most blogs state that the space complexity of a trie is
where:
- $$$N$$$ = number of strings
- $$$L$$$ = maximum length of a string
- $$$R$$$ = alphabet size (typically $$$26$$$ for lowercase letters)
This is usually justified by:
- The trie can have at most $$$L$$$ levels
- Each string contributes at most one node per level
- Each node stores an array of size $$$R$$$
Hence:
However, this is a very loose bound. Let us analyze this carefully.
Key Observation
At depth $$$d$$$, the number of distinct nodes is at most
because:
- Each node represents a unique prefix of length $$$d$$$
- There are at most $$$R^d$$$ possible prefixes at depth $$$d$$$
- And we cannot have more nodes than strings ($$$N$$$)
Example Calculation
Assume:
Compute nodes per level:
From level 5 onward, the number of nodes is capped by $$$N$$$.
Total Number of Nodes
Let us count nodes:
- Levels 0 to 4: $$$26^0 + 26^1 + 26^2 + 26^3 + 26^4$$$
- Levels 5 to $$$L-1$$$: each can have at most $$$N$$$ nodes
Hence, total nodes:
(We use $$$L-4$$$ because the first 4 levels are counted separately: 1,2,3,4 → 4 levels, so remaining $$$L-4$$$ levels are “full” levels capped by $$$N$$$.)
Total Space Usage
Each node stores an array of size $$$R = 26$$$, so total memory:
Comparison With Naive Bound
Naive bound:
We compare the prefix contribution:
Compute sum:
For $$$N = 10^6$$$:
✅ True.
Hence, the naive bound overestimates memory by about 8×, because it assumes $$$N$$$ nodes at each level, while in reality early levels have far fewer nodes.
Tight Space Complexity
In general, the tight upper bound on the number of nodes is:
So total space:
For fixed alphabet size $$$R$$$:
Takeaway
- $$$O(N \cdot L \cdot R)$$$ is a very loose bound
- Early levels of the trie have far fewer nodes than $$$N$$$
- Real space usage is often ~8× smaller than the naive calculation
- Correct intuition: $$$\min(N, R^d)$$$ nodes at depth $$$d$$$
