Suffix Tree
A suffix tree is a compressed trie of all suffixes of a given string. For a string S of length N with a terminating character (usually dollar sign) not app...
Representing All Suffixes Compactly
A suffix tree is a compressed trie of all suffixes of a given string. For a string S of length N with a terminating character (usually dollar sign) not appearing elsewhere in S, the suffix tree contains exactly N leaves, each corresponding to one suffix. Edges are labeled with substrings (stored as start and end indices into S, not as actual characters), making the total space O(N) despite the potentially quadratic total length of all substrings.
Every internal node in a suffix tree has at least two children. Paths from the root to leaves represent all suffixes. The string spelled out by following any path from the root to a node is called the string label of that node. Every substring of S is a prefix of some suffix, so every substring corresponds to a path starting at the root — this is what makes suffix trees so powerful for substring queries.
Suffix trees can be built in O(N) time using Ukkonen's algorithm (published in 1995), which constructs the suffix tree online (one character at a time) using suffix links and active points. The construction is complex but the resulting structure enables an enormous range of string problems to be solved in linear or near-linear time.
Operations and Applications
Substring search: given pattern P of length M, check if P occurs in S by traversing the suffix tree following edge labels character by character. If traversal succeeds, P is a substring. Time: O(M), independent of N. All occurrences: once P's node is found, the number of leaves in its subtree gives the count of occurrences; DFS on the subtree lists all starting positions. Time: O(M plus number-of-occurrences).
Longest common substring of two strings S and T: build a generalized suffix tree for both strings (using distinct terminators), then find the deepest internal node that has descendant leaves from both strings. The string label of that node is the answer. Time: O(N plus M) using the suffix tree.
Longest repeated substring in S: the deepest internal node in the suffix tree of S has the longest string label, since it has at least two leaf descendants (at least two suffixes share this prefix). Time: O(N) after O(N) construction.
Each of these operations would require O(N times M) or O(N squared) time without suffix trees, showing why they are worth their construction complexity.
Worked Example and Interview Guidance
Worked example: for S equals "banana$", the suffix tree has seven leaves for suffixes "banana$", "anana$", "nana$", "ana$", "na$", "a$", "$". The internal node reached by path "a" has three leaf descendants (suffixes starting with "a" at positions 1, 3, 5). The internal node reached by "ana" has two leaves (positions 1 and 3). The node for "ana" has the deepest string label among nodes with multiple leaves, so "ana" is the longest repeated substring in "banana" — correct.
Suffix trees solve string problems that would otherwise require complicated algorithms: palindrome detection (using a technique called Eertree or by combining with LCA), approximate pattern matching, and DNA sequence alignment.
Interview tip: suffix trees are rarely implemented from scratch in interviews due to the complexity of Ukkonen's algorithm. However, you should know the conceptual structure — that a suffix tree compresses all suffixes into O(N) space using index-labeled edges — and be able to describe how substring search, longest repeated substring, and longest common substring are solved using it. For interviews that require implementation, suffix arrays with LCP arrays are a more approachable alternative.