# Ternary Search Tree Search

# Ternary Search Tree Search

Ternary search tree search stores strings in a tree where each node contains one character and has three children.

The left child stores smaller characters, the middle child continues the current string, and the right child stores larger characters. This combines properties of binary search trees and tries.

## Problem

Given a ternary search tree root `root` and a string key `s`, determine whether `s` is stored as a complete key.

Return true if present, otherwise false.

## Structure

Each node stores:

| field         | meaning                                                |
| ------------- | ------------------------------------------------------ |
| `char`        | character stored at this node                          |
| `left`        | next node for smaller character                        |
| `mid`         | next node for equal character and next string position |
| `right`       | next node for larger character                         |
| `is_terminal` | marks the end of a stored key                          |

## Algorithm

Compare the current query character with the node character.

```text id="ts0q4k"
ternary_search_tree_search(root, s):
    if s is empty:
        return false

    node = root
    i = 0

    while node != null:
        c = s[i]

        if c < node.char:
            node = node.left

        else if c > node.char:
            node = node.right

        else:
            if i == length(s) - 1:
                return node.is_terminal

            i = i + 1
            node = node.mid

    return false
```

## Example

Stored keys:

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

One possible ternary search tree:

```text id="ts1v8p"
        c
        |
        a
       / \
      -   -
       \ 
        t*
       /
      r*
```

A clearer search path for `"car"` is:

| step | query char | node char | action               |
| ---- | ---------- | --------- | -------------------- |
| 1    | c          | c         | equal, go middle     |
| 2    | a          | a         | equal, go middle     |
| 3    | r          | t         | r < t, go left       |
| 4    | r          | r         | equal, terminal true |

The `*` marks a terminal node.

## Correctness

At each node, the current query character is compared with the node character. If it is smaller, only the left subtree can contain a matching continuation. If it is larger, only the right subtree can contain it. If it is equal, the search advances to the next character through the middle child.

This exactly mirrors lexicographic search over strings. When the last character is matched, the terminal flag determines whether the full string, rather than only a prefix, is stored.

Therefore the algorithm returns true exactly when the key exists in the ternary search tree.

## Complexity

Let $L$ be the string length and $h_c$ be the height of character comparison trees at each level.

| case                        | time               |
| --------------------------- | ------------------ |
| balanced character branches | $O(L \log \sigma)$ |
| typical sparse strings      | close to $O(L)$    |
| worst case                  | $O(L + n)$         |

Here $\sigma$ is the alphabet size.

Space complexity for iterative search is:

$$
O(1)
$$

## When to Use

Ternary search trees are useful when:

* keys are strings
* memory use should be lower than a full array based trie
* prefix search is needed
* ordered traversal is useful

Compared to ordinary tries, ternary search trees avoid storing a large child array per node. Compared to hash tables, they preserve prefix and lexicographic operations.

## Implementation

```python id="ts2m7x"
class TSTNode:
    def __init__(self, char):
        self.char = char
        self.left = None
        self.mid = None
        self.right = None
        self.is_terminal = False

def ternary_search_tree_search(root, s):
    if not s:
        return False

    node = root
    i = 0

    while node is not None:
        c = s[i]

        if c < node.char:
            node = node.left
        elif c > node.char:
            node = node.right
        else:
            if i == len(s) - 1:
                return node.is_terminal

            i += 1
            node = node.mid

    return False
```

```go id="ts3k9v"
type TSTNode struct {
	Char       rune
	Left       *TSTNode
	Mid        *TSTNode
	Right      *TSTNode
	IsTerminal bool
}

func TernarySearchTreeSearch(root *TSTNode, s string) bool {
	runes := []rune(s)
	if len(runes) == 0 {
		return false
	}

	node := root
	i := 0

	for node != nil {
		c := runes[i]

		if c < node.Char {
			node = node.Left
		} else if c > node.Char {
			node = node.Right
		} else {
			if i == len(runes)-1 {
				return node.IsTerminal
			}

			i++
			node = node.Mid
		}
	}

	return false
}
```