The Concept#
A trie (also called a prefix tree) stores strings by decomposing them into individual characters. Each edge in the tree represents one character, so every path from the root spells out a prefix or, when a special end-of-word flag is set on the terminal node, a complete word.
The key insight: strings that share a prefix share the same path from the root. The words "car", "card", "care", and "careful" all travel through the same c → a → r chain before diverging. That shared structure is what makes prefix queries cheap.
Structure of a trie node#
children maps the next character to its subtree. is_word marks whether the path from the root to this node spells a complete stored word. Without that flag you could not distinguish "car" from "card", since both share the same c → a → r path. The flag on the r node settles it.