Feb 15, 2026

Trie

Overview

A trie stores strings one character per edge. Its root represents the empty prefix, and every other TrieNode represents the prefix formed by following the path from the root to that node. Words sharing a prefix therefore share the same nodes.

A basic TrieNode has two fields:

children: a map from the next character to its child TrieNode. For lowercase English letters, it can instead be a 26-slot array such as TrieNode[] children = new TrieNode[26]. The character determines the slot: 'a' maps to index 0, 'b' to 1, and so on using int index = character - 'a'. The next node is children[index]; a null slot means that character path does not exist.
isWord or isEnd: a boolean indicating that a complete word ends at this node. Without this marker, the trie cannot distinguish a stored word from a prefix of a longer word.

Some problems add fields such as counts for the number of words sharing a prefix or ends for the number of copies ending at a node. These fields are optional and depend on the operations the trie must support.

Insertion, exact search, and prefix search follow exactly one child edge for each input character. A child lookup is O(1) on average with a hash map and O(1) with a fixed array, so processing a string of length L takes O(L) time regardless of how many words the trie contains. The tradeoff is memory: sparse child maps save unused slots, while fixed arrays provide simple, predictable transitions for a small alphabet.

Templates

Start at the root.
At each character, use node.children[character] to move to the next TrieNode.
For insertion, create that child when it does not exist.
Mark the final node with isWord = true.
For exact search, follow every character and require isWord at the final node.
For prefix search, successfully following every character is sufficient.

import java.util.HashMap;
import java.util.Map;

class TrieNode {
	Map<Character, TrieNode> children = new HashMap<>();
	boolean isWord;
}

class Trie {
	private final TrieNode root = new TrieNode();

	public void insert(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			node = node.children.computeIfAbsent(
				character,
				key -> new TrieNode()
			);
		}

		node.isWord = true;
	}

	public boolean search(String word) {
		TrieNode node = find(word);
		return node != null && node.isWord;
	}

	public boolean startsWith(String prefix) {
		return find(prefix) != null;
	}

	private TrieNode find(String text) {
		TrieNode node = root;

		for (char character : text.toCharArray()) {
			node = node.children.get(character);
			if (node == null) {
				return null;
			}
		}

		return node;
	}
}

class TrieNode:
	def __init__(self) -> None:
		self.children: dict[str, TrieNode] = {}
		self.is_word = False

class Trie:
	def __init__(self) -> None:
		self.root = TrieNode()

	def insert(self, word: str) -> None:
		node = self.root

		for character in word:
			node = node.children.setdefault(character, TrieNode())

		node.is_word = True

	def search(self, word: str) -> bool:
		node = self._find(word)
		return node is not None and node.is_word

	def startsWith(self, prefix: str) -> bool:
		return self._find(prefix) is not None

	def _find(self, text: str) -> TrieNode | None:
		node = self.root

		for character in text:
			if character not in node.children:
				return None
			node = node.children[character]

		return node

Problems

208. Implement Trie (Prefix Tree)

Implement insertion, exact lookup, and prefix lookup with a root TrieNode. Each node maps characters to child nodes and uses isEnd to distinguish a complete word from a prefix.

import java.util.HashMap;
import java.util.Map;

class TrieNode {
	boolean isEnd;
	Map<Character, TrieNode> children;

	public TrieNode() {
		isEnd = false;
		children = new HashMap<>();
	}
}

class Trie {
	private final TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	public void insert(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			if (!node.children.containsKey(character)) {
				node.children.put(character, new TrieNode());
			}
			node = node.children.get(character);
		}

		node.isEnd = true;
	}

	public boolean search(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			if (!node.children.containsKey(character)) {
				return false;
			} else {
				node = node.children.get(character);
			}
		}

		return node.isEnd == true;
	}

	public boolean startsWith(String prefix) {
		TrieNode node = root;

		for (char character : prefix.toCharArray()) {
			if (!node.children.containsKey(character)) {
				return false;
			} else {
				node = node.children.get(character);
			}
		}

		return true;
	}
}

class TrieNode:
    def __init__(self):
        self.isEnd = False
        self.children = {} # letter to child TrieNode dictionary

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            else:
                node = node.children[char]
        return node.isEnd == True

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            else:
                node = node.children[char]
        return True

1804. Implement Trie II (Prefix Tree)

Extend a trie with duplicate counts, prefix counts, and erasure. Increment counts at every node reached during insertion and ends at the terminal node. Erasing walks the same path and decrements those counters.

import java.util.HashMap;
import java.util.Map;

class TrieNode {
	int counts;
	int ends;
	Map<Character, TrieNode> children;

	public TrieNode() {
		counts = 0;
		ends = 0;
		children = new HashMap<>();
	}
}

class Trie {
	private final TrieNode root;

	public Trie() {
		root = new TrieNode();
	}

	public void insert(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			if (!node.children.containsKey(character)) {
				node.children.put(character, new TrieNode());
			}
			node = node.children.get(character);
			node.counts++;
		}

		node.ends++;
	}

	public int countWordsEqualTo(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			if (!node.children.containsKey(character)) {
				return 0;
			}
			node = node.children.get(character);
		}

		return node.ends;
	}

	public int countWordsStartingWith(String prefix) {
		TrieNode node = root;

		for (char character : prefix.toCharArray()) {
			if (!node.children.containsKey(character)) {
				return 0;
			}
			node = node.children.get(character);
		}

		return node.counts;
	}

	public void erase(String word) {
		TrieNode node = root;

		for (char character : word.toCharArray()) {
			node = node.children.get(character);
			node.counts--;
		}

		node.ends--;
		return;
	}
}

class TrieNode:
    def __init__(self):
        self.counts = 0
        self.ends = 0
        self.children = {} # letter to TrieNode dictionary

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.counts += 1
        node.ends += 1

    def countWordsEqualTo(self, word: str) -> int:
        node = self.root
        for char in word:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.ends

    def countWordsStartingWith(self, prefix: str) -> int:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.counts

    def erase(self, word: str) -> None:
        node = self.root
        for char in word:
            node = node.children[char]
            node.counts -= 1
        node.ends -= 1
        return

139. Word Break

Determine whether a string can be segmented into dictionary words. Insert the dictionary into a trie, then use dynamic programming: from each reachable start index, walk the trie forward and mark every encountered word ending as a reachable next index.

import java.util.List;

class Solution {
	private static class Node {
		Node[] children = new Node[26];
		boolean isWord;
	}

	public boolean wordBreak(String s, List<String> wordDict) {
		Node root = new Node();

		for (String word : wordDict) {
			Node node = root;
			for (char character : word.toCharArray()) {
				int index = character - 'a';
				if (node.children[index] == null) {
					node.children[index] = new Node();
				}
				node = node.children[index];
			}
			node.isWord = true;
		}

		boolean[] reachable = new boolean[s.length() + 1];
		reachable[0] = true;

		for (int start = 0; start < s.length(); start++) {
			if (!reachable[start]) {
				continue;
			}

			Node node = root;
			for (int end = start; end < s.length(); end++) {
				node = node.children[s.charAt(end) - 'a'];
				if (node == null) {
					break;
				}
				if (node.isWord) {
					reachable[end + 1] = true;
				}
			}
		}

		return reachable[s.length()];
	}
}

from typing import List

class Node:
	def __init__(self) -> None:
		self.children: dict[str, Node] = {}
		self.is_word = False

class Solution:
	def wordBreak(self, s: str, wordDict: List[str]) -> bool:
		root = Node()

		for word in wordDict:
			node = root
			for character in word:
				node = node.children.setdefault(character, Node())
			node.is_word = True

		reachable = [False] * (len(s) + 1)
		reachable[0] = True

		for start in range(len(s)):
			if not reachable[start]:
				continue

			node = root
			for end in range(start, len(s)):
				if s[end] not in node.children:
					break
				node = node.children[s[end]]

				if node.is_word:
					reachable[end + 1] = True

		return reachable[-1]