Skip to interview prep
Apexed

322. Compare tries, ternary search trees and suffix trees.

MediumString algorithms

Technical
Show model answer

A trie stores a set of strings with one edge per character; lookup, insert and prefix queries take O(L) for a word of length L, independent of how many words are stored. Its downside is memory: each node may hold an array of σ child pointers (or a hash map). A ternary search tree stores one character per node with less, equal and greater children, using far less memory while still supporting prefix and near-neighbour queries, at a cost of about O(L + log n) comparisons on average.

A suffix tree is a compressed trie of all suffixes of one text. It can be built in O(n) (Ukkonen’s algorithm) and then answers "does pattern P occur?" in O(|P|), plus longest repeated substring, longest common substring and many other queries. It uses O(n) nodes but with large constants (often 10–20 bytes per character or more), which is why suffix arrays with LCP arrays are popular in practice.

Compare tries, ternary search trees and suffix trees. — Data structures & algorithms interview question — Apexed