# 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? – Paresh Nov 27 '12 at 6:22
• I have a very rough idea of McCreight's suffix tree construction algorithm. – Wuschelbeutel Kartoffelhuhn Nov 27 '12 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 '12 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....
• Yes it is ${n \choose 2}=n(n-1)/2=\Theta(n^2)$. – A.Schulz Nov 27 '12 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. – Paresh Nov 27 '12 at 8:01
• @Paresh How are you getting $1+\binom{n+1}{2}$? On wiki it is given as $\binom{n+1}{2}$. – user1771809 Nov 29 '12 at 10:50