Trie (Prefix Tree) explained step-by-step: node structure, string insertion, prefix search, autocomplete, complexity, and JavaScript implementation.
A Trie (pronounced "try" or prefix tree) is a tree-like data structure used to store associative keys (typically strings). Unlike a binary search tree, nodes in a Trie do not store keys directly; instead, a node’s position in the tree defines the key associated with it.
All descendants of a node share a common string prefix. This enables fast O(L) insertion, exact lookup, and prefix matching (autocomplete) where L is the length of the string.
Create a root node containing a map/dictionary of children character links and an isEndOfWord boolean flag.
To insert a word, iterate through its characters. If a character link does not exist from the current node, create a new child TrieNode.
After creating/navigating to the node corresponding to the final character, set its isEndOfWord flag to true.
To check if a prefix exists, traverse down character links. If all characters are present in sequence, the prefix exists in the Trie.
1class TrieNode {2 constructor() {3 this.children = {};4 this.isEndOfWord = false;5 }6}7 8class Trie {9 constructor() {10 this.root = new TrieNode();11 }12 13 insert(word) {14 let current = this.root;15 for (const char of word) {16 if (!current.children[char]) {17 current.children[char] = new TrieNode();18 }19 current = current.children[char];20 }21 current.isEndOfWord = true;22 }23 24 search(word) {25 let current = this.root;26 for (const char of word) {27 if (!current.children[char]) return false;28 current = current.children[char];29 }30 return current.isEndOfWord;31 }32 33 startsWith(prefix) {34 let current = this.root;35 for (const char of prefix) {36 if (!current.children[char]) return false;37 current = current.children[char];38 }39 return true;40 }41}Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Step-by-step tree structure & key lookup path inspector
Test your understanding of Trie (Prefix Tree) complexity and step mechanics.
Q1.What is the time complexity to search for a word of length L in a Trie?
Q2.Why is a Trie preferred over a Hash Table for dictionary autocomplete?
Apply Trie (Prefix Tree) to real coding interview questions.
Implement a Trie with insert, search, and startsWith methods.
Design a data structure that supports adding new words and finding if a string matches any previously added string, including wildcard '.' dots.