# Why does a suffix tree have a linear number of nodes (relative to input string size)?

Aren't there $n^2$ unique substrings of a string (irrespective of the alphabet size)? Perhaps the number of unique suffix substrings is less than the number of unique substrings of a string.

• Have you read some articles/papers/tutorials explaining how suffix trees can be constructed in linear time with linear space complexity? Nov 27, 2012 at 6:22
• I have a very rough idea of McCreight's suffix tree construction algorithm. Nov 27, 2012 at 6:25
• They may be $\approx n^2$ many substrings, but suffix strings only store suffices, which there are only linearly many of.
– Raphael
Nov 27, 2012 at 8:22

For a text of length $n$ we have up to $1+{ n+1 \choose 2}$ different substrings, however there are only $n+1$ suffixes (for every suffix you can pick the position where it starts).

I assume you consider the compressed suffix tree (edge labels are words). This is a tree with $n+1$ leaves and every internal node has at least two children. Thus we have less interior nodes than leaves an therefore the tree has size $O(n)$.

Notice that in the uncompressed version (edge labels a characters) with a large alphabet, you can have super-linear suffix trees. For example, consider the text abcdefghijk....

• thanks for your answer. is n choose 2 (i.e., the max number of unique substrings in a string) order of n^2? Nov 27, 2012 at 7:53
• Yes it is ${n \choose 2}=n(n-1)/2=\Theta(n^2)$. Nov 27, 2012 at 7:56
• @A.Schulz I think there is a small mistake in the number of unique substrings. It should be $1 + {{n+1} \choose 2}$. ${n \choose 2}$ does not take into account single alphabet substrings. Nov 27, 2012 at 8:01
• @Paresh How are you getting $1+\binom{n+1}{2}$? On wiki it is given as $\binom{n+1}{2}$. Nov 29, 2012 at 10:50
• How is it guaranteed that the internal nodes will have at least 2 children? As per my understanding, number of children depends on the number of suffixes that start from that node. How did you count the children for the internal nodes?
– Clyt
Mar 20, 2019 at 4:13