How Do Trie Node Counts Measure Shared Prefixes?
A count on each trie node records how many inserted words pass through it. Prefix queries and longest common prefixes then become path walks.
Words share a trie path until their characters differ. Store on each node the number of inserted words that pass through it. The root count is the total number of words; after one character, the child count is the number sharing that one-character prefix.
Node meaning and insertion
Press Run to execute this example. Use console.log to print a value.
The invariant after inserting any number of words is that a node's prefixCount equals the number of insertions whose spelling includes the root-to-node path as a prefix. isWord answers a different question: whether a word ends exactly there.
Two queries
To count a queried prefix, walk its characters. A missing edge returns 0; otherwise return the final node's count. The empty query ends at the root and therefore counts every inserted word.
For the longest common prefix of W words, continue from the root while there is exactly one next character whose node count is W. Stop at a branch or a lower count. For flower, flow, and flight, counts remain 3 through f and l, then split, so the answer is "fl".
Building takes O(C) time and space for C inserted characters before sharing. A query of length L takes O(L) time. Finding the common prefix takes O(P · A) with plain object child scans, where P is the returned prefix length and A is the number of outgoing edges inspected per node.
Edge cases and TypeScript details
- Every node must receive a fresh
childrenobject. - An empty word marks the root's
isWord; it also contributes to the root count. - Duplicate insertions increase counts repeatedly unless the contract deduplicates words first.
Record<string, Node | undefined>makes a missing edge explicit without a type assertion.- Normalize Unicode first if canonically equivalent spellings should share a path.
Optional enrichment
Add deletion by decrementing each node on the exact word path. An end counter is needed if duplicate insertions must be deleted independently.