This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#208) before relying on it.

Implement Trie (Prefix Tree)

An interactive visualization of the Trie data structure. Watch how insert, search, and startsWith operations traverse the tree character by character, creating nodes and following paths.

Trie LeetCode 208 ↗ Medium

The Problem

A trie (pronounced "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class:

• Trie() — Initializes the trie object.
• void insert(String word) — Inserts the string word into the trie.
• boolean search(String word) — Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
• boolean startsWith(String prefix) — Returns true if there is a previously inserted string that has the prefix prefix, and false otherwise.

Interactive Visualization

Operation

Word / Prefix

Speed:

Trie Structure

Code

class TrieNode {    val children = mutableMapOf<Char, TrieNode>()    var isEnd = false}class Trie {    private val root = TrieNode()    fun insert(word: String) {        var node = root        for (char in word) {            if (char !in node.children) {                node.children[char] = TrieNode()            } node = node.children[char]!!        } node.isEnd = true    }    fun search(word: String): Boolean {        var node = root        for (char in word) {            if (char !in node.children)                return false            node = node.children[char]!!        } return node.isEnd    }    fun startsWith(prefix: String): Boolean {        var node = root        for (char in prefix) {            if (char !in node.children)                return false            node = node.children[char]!!        } return true    }}

class TrieNode:    def __init__(self):        self.children = {}        self.is_end = Falseclass Trie:    def __init__(self):        self.root = TrieNode()    def insert(self, word):        node = self.root        for char in word:            if char not in node.children:                node.children[char] = TrieNode()            node = node.children[char]        node.is_end = True    def search(self, word):        node = self.root        for char in word:            if char not in node.children:                return False            node = node.children[char]        return node.is_end    def startsWith(self, prefix):        node = self.root        for char in prefix:            if char not in node.children:                return False            node = node.children[char]        return True

Current Step

Choose an operation and press Step or Play to begin.

How It Works

Trie Structure

A trie is a tree-like data structure where each node represents a single character. The root node is empty, and each path from root to a node represents a prefix of one or more stored words. Nodes marked as "end of word" (shown with a green ring) indicate that the path from root to that node forms a complete word that was explicitly inserted.

Insert

Starting from the root, walk through each character of the word. If a child node for that character already exists, follow it. If not, create a new node. After processing all characters, mark the final node as an end-of-word node. This means words that share prefixes (like "apple" and "app") share the same path up to the point where they diverge.

Search

Starting from the root, follow the path character by character. If at any point the required child node does not exist, return False immediately — the word was never inserted. If we successfully traverse all characters, we check whether the final node is marked as end-of-word. A prefix like "ap" may exist as a path in the trie (because "apple" was inserted), but search("ap") returns False because that node is not marked as an end of word.

StartsWith

Identical to search, but we do not check the end-of-word flag. If we can follow the entire prefix path without hitting a missing node, the prefix exists and we return True.

Complexity

Time (all ops) O(L)

Space O(N * L)

Each operation — insert, search, startsWith — processes exactly L characters (the length of the word or prefix), so each runs in O(L) time regardless of how many words are stored. Space is O(N * L) in the worst case where N words of length L share no common prefixes. In practice, shared prefixes significantly reduce space usage — that is precisely the advantage of a trie over storing each word independently.