Published by Dimitris Kougioumtzis · Updated
Share letter prefixes between words, count unique words below each node, and prune a deleted word only when its branch is no longer used.
Share prefixes between words and mark only complete words as terminal. Prefix counts track unique words below each node. Deletion clears a terminal marker and prunes a suffix only when no surviving word uses it.
When to use Trie insertion, prefix search and deletion
Teaching prefix lookup, dictionary word membership and safe removal of shared prefixes.
Choosing an alternative
Hash lookup checks complete keys; a trie follows characters and directly supports prefix queries. A node can be a complete word and still have children.
Worked example: input and state changes
Example input
an,ant,as | an | a
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Root starts empty. A star marks a complete word; node values count unique words under that prefix.
State at this checkpoint
{ "values": [ 0 ], "active": [], "kind": "graph", "chosen": [], "visited": [], "nodeLabels": [ "root" ] }Step 3: Mark an as a complete word and increment prefix counts.
State at this checkpoint
{ "values": [ 1, 1, 1 ], "active": [ 2 ], "kind": "graph", "chosen": [], "visited": [ 2 ], "nodeLabels": [ "root", "a", "an *" ] }Step 5: Mark ant as a complete word and increment prefix counts.
State at this checkpoint
{ "values": [ 2, 2, 2, 1 ], "active": [ 3 ], "kind": "graph", "chosen": [], "visited": [ 2, 3 ], "nodeLabels": [ "root", "a", "an *", "ant *" ] }Step 8: Deleted an; shared prefixes remain.
State at this checkpoint
{ "values": [ 2, 2, 1, 1, 1 ], "active": [], "kind": "graph", "chosen": [], "visited": [ 3, 4 ], "nodeLabels": [ "root", "a", "an", "as *", "ant *" ] }Step 10: Prefix a: 2 stored word(s); exact word no.
State at this checkpoint
{ "values": [ 2, 2, 1, 1, 1 ], "active": [ 1 ], "kind": "graph", "chosen": [], "visited": [ 3, 4 ], "nodeLabels": [ "root", "a", "an", "as *", "ant *" ], "result": 2, "exact": false }
Expected final state
Prefix a: 2 stored word(s); exact word no.
Complexity and input bounds
Family: Trees. Time complexity: O(word length) per operation.
Implementation detail: The view accepts lowercase words with at most eight insertion letters total, giving at most nine nodes. Stars mark terminals; node values are prefix counts. Downloads accept letter codes 0..25, return surviving prefix count and serialize a canonical BFS trie. An empty download prefix counts every stored word.
Space complexity: O(alphabet size times nodes) array storage in portable versions; object maps in the Python version; saved frames add space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..4 lowercase words, at most eight letters total | word to delete | prefix to query. Each word/prefix has 1..4 letters.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Do not count duplicate words twice. Removing a short word must preserve longer words sharing it. Removing a long word must preserve a terminal shorter prefix.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | // Trie set over letter codes 0..25 (a..z): words 0..4; lengths 1..4; at most 8 total insertion letters; letters is their concatenation. deleteLetters and prefix have lengths 0..4 (empty prefix counts all words; empty word is never stored). Duplicate words ignored. Delete one word, pruning only unused branches, then return number of surviving words with the prefix. Output capacity 256: [0] prefix count, [1] exact-word flag, [2] deletion flag, [3] live node count. Then 28 fields per BFS node: terminal flag, 26 alphabetic child BFS indices (-1 absent), subtree word count. Root is node 0; unused records zero. At most nine nodes fit the 256-slot child buffer. Operations O(word length), serialization O(26 * nodes), auxiliary space O(26 * nodes). Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(letters, lengths, words, deleteLetters, deleteLength, prefix, prefixLength, output) { let children = Array(256).fill(0); let terminal = Array(256).fill(0); let counts = Array(256).fill(0); let path = Array(256).fill(0); let queue = Array(256).fill(0); let mapping = Array(256).fill(0); let nodes = 1; let offset = 0; let u = 0; let v = 0; let letter = 0; let step = 0; let deleted = 0; let exists = 1; let result = 0; let exact = 0; let head = 0; let tail = 1; let base = 0; for (let word = 0; word < words; word++) { u = 0; path[0] = 0; for (let i = 0; i < lengths[word]; i++) { letter = letters[offset++]; if (children[u * 26 + letter] == 0) { children[u * 26 + letter] = nodes++; } u = children[u * 26 + letter]; path[i + 1] = u; } if (terminal[u] == 0) { terminal[u] = 1; for (let i = 0; i <= lengths[word]; i++) { counts[path[i]]++; } } } u = 0; path[0] = 0; for (step = 0; step < deleteLength; step++) { v = children[u * 26 + deleteLetters[step]]; if (v == 0) { break; } u = v; path[step + 1] = u; } if (step == deleteLength && terminal[u] != 0) { terminal[u] = 0; deleted = 1; for (let i = 0; i <= deleteLength; i++) { counts[path[i]]--; } for (let i = deleteLength - 1; i >= 0; i--) { if (counts[path[i + 1]] != 0) { break; } children[path[i] * 26 + deleteLetters[i]] = 0; } } u = 0; for (let i = 0; i < prefixLength; i++) { v = children[u * 26 + prefix[i]]; if (v == 0) { exists = 0; break; } u = v; } if (exists != 0) { result = counts[u]; exact = terminal[u]; } for (let i = 0; i < 256; i++) { output[i] = 0; } queue[0] = 0; mapping[0] = 0; while (head < tail) { u = queue[head]; base = 4 + 28 * head; output[base] = terminal[u]; output[base + 27] = counts[u]; for (let i = 0; i < 26; i++) { output[base + 1 + i] = -1; v = children[u * 26 + i]; if (v != 0) { mapping[v] = tail; queue[tail++] = v; output[base + 1 + i] = mapping[v]; } } head++; } output[0] = result; output[1] = exact; output[2] = deleted; output[3] = tail; return result; } |
Source
Classic primary research that introduced the term trie. This is not a claim that prefix trees were first invented in 1960; the playground adds bounded set semantics, prefix counts and deletion.
- Trie memory
Edward Fredkin (1960). Classic research paper.