# Tries

A **trie** is a tree data structure often used to store strings.
Every leaf of the trie represents one string. Each node on the path
from root to leaf is labeled with exactly one character of the
string. Information on this page is taken from section 12.3 of
*The Algorithm Design Manual* by Steven S. Skiena.

Here's a trie on strings *the*, *their*, *there*,
*was*, and *when*.

Tries are useful for testing whether a given query string
*q* is in the set. We traverse the trie from the root along
branches defined by successive characters of *q*. If a branch
does not exist in the trie, then *q* cannot be in the set of
strings. Otherwise we find *q* in |q| character comparisons
*regardless* of how many strings are in the trie.

A **suffix tree** is a trie of all proper suffixes of \(S\). A
suffix tree enables one to test whether \(q\) is a substring of
\(S\), because any substring of \(S\) is a prefix of some suffix.
Here's a suffix tree on *elliot*.

Constructed naively, a suffix tree requires \(O(n^2)\) time and
space. A **compressed trie**, however, requires linear space.
This trie is obtained by joining chains of single nodes. The nodes
of a compressed trie also often store index ranges instead of actual
strings. Here's a compressed suffix tree on *elliot*.