Autocomplete System with Trie in DSA Javascript - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

Create root node

↓

For each word

↓

For each char in word

↓

If char node missing

↓

Create node

↓

Mark end of word

↓

Search prefix in Trie

↓

Traverse nodes for prefix chars

↓

If prefix found

↓

Collect all words

↓

Return autocomplete suggestions

Insert words character by character into the Trie, marking ends. To autocomplete, traverse prefix nodes, then collect all words below.

Execution Sample

DSA Javascript

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

Defines a Trie node with children map and end-of-word marker.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Create root node	root	head -> root	{root}
2	Insert 'cat'	root -> c -> a -> t (isEnd=true)	head -> root -> c -> a -> t	{root} └─ c └─ a └─ t*
3	Insert 'car'	root -> c -> a -> t (isEnd=true), r (isEnd=true)	head -> root -> c -> a -> r	{root} └─ c └─ a ├─ t* └─ r*
4	Insert 'dog'	root -> c -> a -> t*, r*; d -> o -> g (isEnd=true)	head -> root -> d -> o -> g	{root} ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
5	Search prefix 'ca'	Same as above	Traverse root -> c -> a	At node 'a' under 'c'
6	Collect words from 'ca'	Same as above	Collect 'cat', 'car'	Suggestions: ['cat', 'car']
7	Search prefix 'do'	Same as above	Traverse root -> d -> o	At node 'o' under 'd'
8	Collect words from 'do'	Same as above	Collect 'dog'	Suggestions: ['dog']
9	Search prefix 'z'	Same as above	Traverse root -> z (missing)	No node found, return []

💡 All words inserted and searched; traversal stops when prefix node missing or all suggestions collected.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	Final
root	{}	{c: {...}}	{c: {...}}	{c: {...}, d: {...}}	{c: {...}, d: {...}}	{c: {...}, d: {...}}	{c: {...}, d: {...}}
currentNode	root	node at 't' in 'cat'	node at 'r' in 'car'	node at 'g' in 'dog'	node at 'a' in 'ca'	node at 'o' in 'do'	null (prefix 'z' missing)
suggestions	[]	[]	[]	[]	['cat', 'car']	['dog']	[]

Key Moments - 3 Insights

Why do we mark the end of a word in the Trie?

Marking end of word (isEnd=true) lets us know when a full word finishes. Without it, we can't distinguish 'car' from 'carpet' prefix. See steps 2-4 in execution_table where nodes exist but only some have isEnd=true.

What happens if the prefix is not found in the Trie?

If prefix nodes are missing during traversal (step 9), we return an empty list immediately because no words start with that prefix.

How do we collect all words starting with a prefix?

After reaching the prefix node (steps 5 and 7), we recursively explore all child nodes and collect words where isEnd=true. This is shown in steps 6 and 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which new branch is added to the Trie?

A A branch for 'c' -> 'a' -> 'r'

B A branch for 'c' -> 'a' -> 't'

C A branch for 'd' -> 'o' -> 'g'

D No new branch added

💡 Hint

Check the Visual State column at step 4 showing the new 'd' branch.

At which step does the system return suggestions for prefix 'ca'?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the Operation and Visual State columns where suggestions are collected for 'ca'.

If we search prefix 'do' but 'dog' was not inserted, what would happen at step 8?

A Suggestions would be empty []

B Traversal would fail at root

C Suggestions would be ['dog']

D An error would occur

💡 Hint

Refer to step 9 where missing prefix returns empty list.

Concept Snapshot

Autocomplete with Trie:
- Insert words char-by-char into Trie nodes
- Mark end of word with isEnd=true
- To autocomplete, traverse prefix nodes
- Collect all words below prefix node
- Return list of suggestions
- Efficient prefix search and retrieval

Full Transcript

This visualization shows how an autocomplete system uses a Trie data structure. We start by creating a root node. Each word is inserted character by character, creating new nodes if needed, and marking the end of the word. For example, inserting 'cat' creates nodes for 'c', 'a', and 't' with 't' marked as end. Inserting 'car' shares 'c' and 'a' nodes, then adds 'r' node marked as end. Searching for a prefix like 'ca' traverses nodes 'c' and 'a', then collects all words below, such as 'cat' and 'car'. If prefix nodes are missing, no suggestions are returned. This method efficiently finds autocomplete suggestions by prefix traversal and collecting words from the Trie.