# 2.20 Tries

A trie is a tree structure for storing a set of strings so that common prefixes are shared. Each edge corresponds to a symbol, and each node represents a prefix. Tries support fast insertion, lookup, prefix queries, and lexicographic traversal.

## Problem

Maintain a dynamic set of strings and support:

```text id="y1n2qr"
Insert(s)
Contains(s)
HasPrefix(p)
List all strings with prefix p
```

A naive approach compares strings directly and costs `O(length)` per comparison. A trie also costs `O(length)` per operation but can answer prefix queries efficiently and avoid repeated prefix comparisons across many strings.

## Node Structure

For lowercase ASCII letters, each node can have up to 26 children.

```go id="m6d9ap"
type Node struct {
	next [26]*Node
	end  bool
}

type Trie struct {
	root *Node
}

func NewTrie() *Trie {
	return &Trie{root: &Node{}}
}
```

`end` marks that a complete word ends at this node.

## Insert

```go id="z8q3lw"
func (t *Trie) Insert(s string) {
	cur := t.root

	for i := 0; i < len(s); i++ {
		idx := s[i] - 'a'

		if cur.next[idx] == nil {
			cur.next[idx] = &Node{}
		}

		cur = cur.next[idx]
	}

	cur.end = true
}
```

Invariant:

```text id="k5w0hz"
After processing s[0:i], cur represents that prefix in the trie
```

## Search Exact String

```go id="p7c2sn"
func (t *Trie) Contains(s string) bool {
	cur := t.root

	for i := 0; i < len(s); i++ {
		idx := s[i] - 'a'

		if cur.next[idx] == nil {
			return false
		}

		cur = cur.next[idx]
	}

	return cur.end
}
```

The `end` flag ensures that `"app"` is distinguished from `"apple"`.

## Prefix Query

```go id="z9k4ru"
func (t *Trie) HasPrefix(p string) bool {
	cur := t.root

	for i := 0; i < len(p); i++ {
		idx := p[i] - 'a'

		if cur.next[idx] == nil {
			return false
		}

		cur = cur.next[idx]
	}

	return true
}
```

Invariant:

```text id="r6m2ps"
If traversal reaches depth i, prefix p[0:i] exists in the trie
```

## Collect Words with a Prefix

First reach the node representing the prefix, then perform DFS.

```go id="d3v8nk"
func (t *Trie) WordsWithPrefix(p string) []string {
	cur := t.root

	for i := 0; i < len(p); i++ {
		idx := p[i] - 'a'

		if cur.next[idx] == nil {
			return nil
		}

		cur = cur.next[idx]
	}

	var out []string
	var dfs func(*Node, []byte)

	dfs = func(n *Node, path []byte) {
		if n.end {
			out = append(out, string(path))
		}

		for i := 0; i < 26; i++ {
			if n.next[i] != nil {
				dfs(n.next[i], append(path, byte('a'+i)))
			}
		}
	}

	dfs(cur, []byte(p))
	return out
}
```

Invariant:

```text id="h8v1gj"
path always represents the string corresponding to the current node
```

## Complexity

Let `L` be the length of the string.

```text id="u5x9tw"
Insert:      O(L)
Contains:    O(L)
HasPrefix:   O(L)
Enumeration: O(total output size)
Space:       O(total characters inserted)
```

Each node corresponds to a unique prefix.

## Space Considerations

A dense `[26]*Node` array is fast but can waste memory when many children are unused.

Alternative: use a map.

```go id="b1r7yv"
type Node struct {
	next map[byte]*Node
	end  bool
}
```

Trade-off:

```text id="l3q5xm"
array: faster, predictable memory
map:   smaller memory for sparse data
```

## Deletion

To delete a string, clear the `end` flag and optionally prune nodes.

```go id="q6f3zn"
func (t *Trie) Delete(s string) {
	t.delete(t.root, s, 0)
}

func (t *Trie) delete(n *Node, s string, i int) bool {
	if i == len(s) {
		if !n.end {
			return false
		}
		n.end = false
		return isEmpty(n)
	}

	idx := s[i] - 'a'
	child := n.next[idx]

	if child == nil {
		return false
	}

	shouldDelete := t.delete(child, s, i+1)

	if shouldDelete {
		n.next[idx] = nil
		return !n.end && isEmpty(n)
	}

	return false
}

func isEmpty(n *Node) bool {
	for i := 0; i < 26; i++ {
		if n.next[i] != nil {
			return false
		}
	}
	return true
}
```

Deletion removes nodes that are no longer needed.

## Compressed Trie (Radix Tree)

Instead of one character per edge, store strings on edges.

This reduces height and memory usage when many nodes have a single child.

Example:

```text id="y4n1xp"
"apple"
"app"
```

can share a single path `"app"`.

Radix trees are more complex but more memory-efficient.

## Trie for Integers (Bitwise Trie)

Tries can store integers by bits.

Each level corresponds to a bit position.

Used in problems like:

```text id="h9c3wq"
maximum XOR pair
```

```go id="y3b8gn"
type BitNode struct {
	next [2]*BitNode
}
```

Traverse from most significant bit to least significant bit.

## Common Pitfalls

Not marking word termination leads to prefix confusion.

Assuming fixed alphabet without validating input can cause index errors.

Using recursion for DFS without considering stack depth for large tries.

Memory usage grows with total inserted characters. Tries are not suitable for very large vocabularies without compression.

Mixing byte-based indexing with Unicode strings produces incorrect results for non-ASCII input.

## Design Pattern

Trie operations follow:

1. Traverse by characters
2. Create nodes on demand
3. Use `end` to mark complete entries
4. Use DFS for enumeration

The invariant is always that a path from root to a node represents a prefix.

## Takeaway

A trie organizes strings by shared prefixes. It provides efficient prefix queries and predictable `O(L)` operations. Use array-backed nodes for small alphabets and maps for sparse ones. For large datasets, consider compressed tries or alternative structures such as hash tables or suffix arrays.