# Trie Search

# Trie Search

Trie search locates a key by following a path defined by its characters. Each edge corresponds to one symbol from the alphabet. A node represents a prefix of stored keys.

Search cost depends on the key length, not on the number of stored keys.

## Problem

Given a trie `root` and a string key `s`, determine whether `s` exists as a stored key.

Return true if present, otherwise false.

## Structure

Each node contains:

| field         | meaning                          |
| ------------- | -------------------------------- |
| `children`    | map from character to child node |
| `is_terminal` | marks the end of a stored key    |

A path from the root to a node corresponds to a prefix of some key.

## Algorithm

Start at the root. For each character in the string, follow the corresponding child pointer. If any character transition is missing, the key is absent. After processing all characters, check the terminal flag.

```text id="tr0p6k"
trie_search(root, s):
    node = root

    for c in s:
        if c not in node.children:
            return false
        node = node.children[c]

    return node.is_terminal
```

## Example

Insert keys:

| key   |
| ----- |
| "cat" |
| "car" |
| "dog" |

Trie structure:

```text id="tr1m9q"
(root)
  ├─ c
  │   └─ a
  │       ├─ t (terminal)
  │       └─ r (terminal)
  └─ d
      └─ o
          └─ g (terminal)
```

Search for `"car"`:

| step | char | action        |
| ---- | ---- | ------------- |
| 1    | c    | go to child c |
| 2    | a    | go to child a |
| 3    | r    | go to child r |
| end  | -    | terminal true |

Search for `"cap"` fails at character `p`.

## Correctness

Each node represents exactly one prefix. Following the sequence of characters in the key leads to the unique node representing that prefix.

If at any step a character transition does not exist, no stored key has that prefix, so the key is absent. If all characters are consumed and the node is marked terminal, the key exists. If the node is not terminal, the prefix exists but not as a complete key.

## Complexity

Let $L$ be the length of the key.

| case   | time   |
| ------ | ------ |
| search | $O(L)$ |

Space complexity for search is constant:

| version   | space  |
| --------- | ------ |
| iterative | $O(1)$ |
| recursive | $O(L)$ |

## When to Use

Trie search is useful when:

* keys are strings or sequences
* prefix queries are important
* many keys share common prefixes
* lookup time should depend on key length rather than number of keys

Compared to hash tables, tries support ordered traversal and prefix operations.

## Implementation

```python id="tr2k7x"
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_terminal = False

def trie_search(root, s):
    node = root

    for c in s:
        if c not in node.children:
            return False
        node = node.children[c]

    return node.is_terminal
```

```go id="tr3n8v"
type TrieNode struct {
	Children   map[rune]*TrieNode
	IsTerminal bool
}

func TrieSearch(root *TrieNode, s string) bool {
	node := root

	for _, c := range s {
		next, ok := node.Children[c]
		if !ok {
			return false
		}
		node = next
	}

	return node.IsTerminal
}
```