Tries

A trie stores a set of sequences as one tree where every edge carries a symbol and every path from the root spells a prefix. Words that begin the same way share nodes, so a lookup costs the length of the word, not the size of the set.

Node holds	C++	Python	Java
Fixed alphabet	array<int, 26>	list of 26	TrieNode[]
Sparse alphabet	unordered_map	dict	HashMap
Word ends here	bool	bool	boolean

No standard library ships a trie, so the node is the whole design. A fixed array per node is fastest on a small alphabet like the 26 lowercase letters, while a hash map per node fits a wide or sparse alphabet. Always keep the end-of-word flag separate from whether a node has children, because a stored word can also be a prefix of a longer one, and without that flag the trie cannot tell a full word from a bare prefix.

Operation	Trie	Hash set
Insert or find a word of length $L$	$O(L)$	$O(L)$
Every word under a prefix	$O(L + \text{hits})$	$O(nL)$
Memory	one node per distinct prefix	one entry per word

Use one when the question is about prefixes rather than whole strings, such as finding the shortest stored prefix that matches a word, or checking whether every prefix of a word is also in the dictionary. When the symbols are the bits of an integer instead of letters, that is a binary trie, covered in Tier 3.

The problems below start with scanning for the longest shared prefix directly, move to building a trie of root words to replace words by their shortest matching prefix, and end with finding the longest word that can be built one letter at a time from other words in the trie.