Trie Structure

A Trie is a tree-like data structure used to store strings by their prefixes. It is also called a prefix tree.

Instead of storing each word as one full string, a Trie stores one character per level. Words that share the same prefix share the same path in the tree.

Example

If we insert:

ball
bat
do
doll
dorm

The Trie shares common prefixes:

root
├── b
│   └── a
│       ├── l
│       │   └── l  end
│       └── t      end
└── d
    └── o          end
        ├── l
        │   └── l  end
        └── r
            └── m  end

Node Shape

Each Trie node usually stores:

class TrieNode {
  constructor() {
    this.keys = new Map();
    this.end = false;
  }
}

• keys: maps a character to the next Trie node.
• end: marks whether the current node completes a full word.

The end flag is important because a prefix is not always a full word.

For example, after inserting "ball":

b -> a -> l -> l

"ba" exists as a path, but it should not count as a word unless its node has end = true.

Common Operations

Insert

To insert a word:

1. Start at the root.
2. For each character, create a child node if it does not exist.
3. Move to that child node.
4. After the last character, mark the node as end = true.

Search Full Word

To check whether a word exists:

1. Start at the root.
2. Follow each character in order.
3. If any character path is missing, return false.
4. After the final character, return true only if end = true.

Prefix Search

To check whether a prefix exists:

1. Follow each character in the prefix.
2. If all characters exist as a path, return true.
3. Unlike full-word search, the final node does not need end = true.

Interview Explanation

A Trie is useful when we need fast prefix-based operations. It trades extra memory for faster lookups over sets of strings.

Good use cases:

• Autocomplete
• Spell check
• Dictionary word search
• Prefix matching
• Word search on a board, often combined with DFS

Complexity

Let k be the length of the word.

• Insert: O(k)
• Search word: O(k)
• Search prefix: O(k)

The space complexity depends on how many unique character paths are stored. In the worst case, storing many unrelated words can take O(total characters).