A suffix tree answers substring queries in O(m); why do practitioners ship a suffix array instead?
answer
- Both are linear — so compare what?
- Count bytes per character, not operations
- Pointers per node versus one integer
- Pointer chasing punishes the cache
- An LCP array closes most of the query gap
basics
~20 sSuffix arrays win on constants, not asymptotics. A suffix tree costs roughly ten to twenty bytes per character in nodes and pointers; a suffix array is one integer per position, is far friendlier to caches, and with an LCP array it answers most of the same queries.
solid answer
~50 sBoth structures are linear in the O-sense, so the choice is decided by constant factors and by implementation risk. A suffix tree is a compressed tree over all suffixes: it gives O(m) matching, but every node carries child links and bookkeeping, so real implementations land around ten to twenty bytes per input character and every query is a pointer chase across scattered memory. A suffix array is one integer per position — typically four bytes — laid out contiguously, so binary search touches few cache lines. The query gap is smaller than it looks: with an LCP array the binary search drops from O(m log n) to O(m + log n), and a suffix array plus LCP plus a child table can simulate any suffix-tree traversal. Linear-time array construction is also markedly easier to get right than linear-time tree construction.
go deeper
Know that both structures index every suffix of a text and that the array form is a sorted list of offsets while the tree form is an explicit branching structure. The comparison itself is rarely asked this early.
Be able to state both query bounds accurately, including that the array's plain bound carries the pattern length as a multiplier, and that an LCP array reduces it. Name memory per character as the practical difference.
Argue the choice with numbers: bytes per character for each form, cache behaviour of a descent versus a bisection, and the correctness risk of hand-rolling linear-time tree construction on a team that must maintain it.
Frame it as an index-strategy call — what index size the fleet's memory budget permits, whether query latency or footprint is the binding constraint, and whether a compressed self-index is the right next step rather than either plain structure.
## Two structures over the same information A **suffix tree** is a compressed tree containing every suffix of the text as a root-to-leaf path, with each edge labelled by a substring (stored as a pair of text offsets, not as copied characters). It has at most `2n` nodes, is built in O(n) by Ukkonen's algorithm for a constant-size alphabet, and matches a pattern of length `m` in **O(m)** by walking down from the root, then reports all `occ` occurrences by collecting the leaves under the stopping point. A **suffix array** with an **LCP array** carries the same information in flat form: the sorted suffix offsets, plus the shared prefix length of each adjacent pair. It matches in **O(m log n)** naively, or **O(m + log n)** with an LCP-augmented binary search that reuses the characters already known to match on the current bracket's two ends. On paper the tree wins. In production the array is usually what ships. The reason is that asymptotic superiority promises nothing about constants, and here the constants differ by roughly a factor of three to five in memory — on inputs large enough to justify either structure, memory *is* the binding constraint. ## The memory arithmetic A suffix array is one integer per text position. With 32-bit offsets that is four bytes per character, plus the text itself. A suffix tree stores, per internal node, an edge label (two offsets), a parent or suffix link, and some representation of children — an array indexed by alphabet symbol (fast, wasteful), a hash structure, or a sorted child list (compact, slower). Practical figures reported for careful implementations cluster in the ten-to-twenty bytes per character range, and the sloppy ones are far worse. For a 10^8-character text that is the difference between roughly 400 MB of offsets and one to two gigabytes of nodes. Whether the index is resident, memory-mapped, or spilled to storage is decided by exactly this number, and the decision changes the latency profile of every query far more than a `log n` factor does. ## The locality arithmetic The second constant is cache behaviour. A tree descent is a sequence of dependent pointer dereferences into addresses with no spatial relationship — each is a potential cache miss, and misses cannot be overlapped because the next address is not known until the current load returns. A binary search over a contiguous integer array also jumps around, but the range narrows geometrically and the last several steps land inside a handful of cache lines; prefetching and branchless layouts help further. The measured gap between "O(m) with misses everywhere" and "O(m + log n) with good locality" is frequently in the array's favour. ## The implementation-risk arithmetic This one is easy to undersell in an interview and it matters in a team. Linear-time suffix-tree construction is famously subtle — active points, suffix links, edge splitting, and the end-of-string sentinel are all places where a plausible-looking implementation is quietly wrong on some inputs. Linear-time suffix-array construction (SA-IS) is comparatively compact, its output is trivially checkable (verify the permutation is sorted), and prefix doubling gives an easy, obviously-correct O(n log n) fallback to test against. When the structure will be owned by a rotating team rather than its original author, that difference is a genuine engineering argument, not a preference. ## What you actually give up Almost nothing that matters, if you carry the LCP array. The **enhanced suffix array** — suffix array, LCP array, and a small child table — supports top-down and bottom-up traversal of the same tree shape the suffix tree makes explicit, so algorithms formulated on the tree can be transcribed. The honest remainders: - Algorithms whose natural expression *is* tree navigation (matching statistics, some streaming formulations) read more clearly on the tree, and clarity has value when correctness is hard-won. - Multiple texts are handled on a tree by a generalised suffix tree, and on an array by concatenating the texts with distinct separator symbols and mapping offsets back — a workable trick that adds bookkeeping. - For very small texts, none of this matters and you should use whichever you can implement correctly today. And for very large texts the argument continues past both: compressed self-indexes built from the Burrows-Wheeler transform (the FM-index family) shrink the index towards the compressed size of the text itself, trading further constant-factor query time for memory. That is the same tradeoff axis, pushed one notch harder. ## The answer this question is aimed at The weak answer is "the tree is O(m) and the array is O(m log n), so use the tree." It treats an upper bound as a ranking and never asks what a byte costs. The strong answer states the query gap accurately, closes most of it with the LCP array, and then argues from memory, locality and implementation risk — the three places where the real difference lives.
- How does the LCP array narrow the query gap?The LCP-augmented binary search precomputes the shared prefix lengths between the bracket's endpoints and the midpoint, so characters already known to match are never re-compared. That removes the multiplicative pattern length from every step, giving O(m + log n) instead of O(m log n) — close enough to the tree's O(m) that memory becomes the deciding factor.
- When would you still reach for the suffix tree?When the text is small enough that memory is irrelevant, when a trusted implementation already exists, or when the algorithm you need is naturally expressed as tree navigation and transcribing it onto an array plus LCP plus child table would add correctness risk. Teaching and derivation are also clearer on the tree — the array is the deployment form, the tree is often the reasoning form.
- What comes after both when memory is still too tight?Compressed self-indexes built on the Burrows-Wheeler transform, the FM-index family, which store something close to the compressed size of the text while still answering substring queries. You pay a larger constant factor per query and a much harder implementation, in exchange for an index that fits where a plain offset array would not.
Both are maps of the same city. The tree gives turn-by-turn directions but is a heavy bound atlas; the array is a single folded sheet you scan quickly — slightly more work per lookup, and it fits in your pocket.
saying these in an interview costs you the question
- Treats the better asymptotic query bound as settling the choice
- Quotes O(m) for the tree while ignoring pointer-chasing cache misses
- Claims the array cannot do what the tree does, even with an LCP array
- Assumes linear-time tree construction is as easy to get right as the array's
- Never mentions memory per character as a first-class constraint