Prefix Search Using Trie in DSA Typescript - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each char in prefix

↓

Check if char exists in current node children?

No→Prefix not found

Yes↓

Move to child node

↓

After last char, collect all words below

↓

Return list of words with prefix

Start from the root and follow each character of the prefix down the trie. If any character is missing, prefix is not found. Otherwise, collect all words below the last node.

Execution Sample

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isWord: boolean = false;
}

// Insert 'cat', 'car', 'dog'
// Search prefix 'ca'

This code inserts words into a trie and then searches for all words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	root -> c	current = root.children.get('c') created	root └─ c
2	Insert 'cat' char 'a'	root -> c -> a	current = c.children.get('a') created	root └─ c └─ a
3	Insert 'cat' char 't'	root -> c -> a -> t (isWord=true)	current = a.children.get('t') created, mark isWord	root └─ c └─ a └─ t*
4	Insert 'car' char 'c'	root -> c -> a -> t*	current = root.children.get('c') exists	root └─ c └─ a └─ t*
5	Insert 'car' char 'a'	root -> c -> a -> t*	current = c.children.get('a') exists	root └─ c └─ a └─ t*
6	Insert 'car' char 'r'	root -> c -> a -> t*, r (isWord=true)	current = a.children.get('r') created, mark isWord	root └─ c └─ a ├─ t* └─ r*
7	Insert 'dog' char 'd'	root -> c -> a -> t*, r*; d	current = root.children.get('d') created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d
8	Insert 'dog' char 'o'	root -> c -> a -> t*, r*; d -> o	current = d.children.get('o') created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o
9	Insert 'dog' char 'g'	root -> c -> a -> t*, r*; d -> o -> g (isWord=true)	current = o.children.get('g') created, mark isWord	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
10	Search prefix 'ca' char 'c'	Same as above	current = root.children.get('c')	root └─ c (current)
11	Search prefix 'ca' char 'a'	Same as above	current = c.children.get('a')	root └─ c └─ a (current)
12	Collect words below 'a'	Same as above	Traverse children t*, r*	Words found: 'cat', 'car'

💡 Prefix 'ca' fully matched; collected words 'cat' and 'car' from trie nodes.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	Final
current	root	node 't' (end of 'cat')	node 'r' (end of 'car')	node 'g' (end of 'dog')	node 'a' (prefix end)	node 'a'
Trie Size	0	1 word inserted	2 words inserted	3 words inserted	3 words inserted	3 words inserted
Words Found	[]	[]	[]	[]	[]	['cat', 'car']

Key Moments - 3 Insights

Why do we mark isWord only at the last character node?

Because only the last character node represents a complete word. See execution_table rows 3, 6, and 9 where isWord is set.

What happens if a prefix character is missing in children?

The search stops immediately and returns no words. See execution_table row 11 where each prefix char must exist.

How do we collect all words after matching prefix?

We traverse all child nodes recursively from the prefix end node to find nodes marked isWord. See execution_table row 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which new node is created?

A Node 'r' under 'a'

B Node 't' under 'a'

C Node 'd' under root

D Node 'g' under 'o'

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6.

At which step does the prefix search reach the node for 'a'?

A Step 10

B Step 12

C Step 11

D Step 9

💡 Hint

Look at the 'Pointer Changes' column for prefix search steps.

If we searched prefix 'do', what would be the pointer position after matching?

A Node 'd'

B Node 'o'

C Node 'g'

D Root node

💡 Hint

Follow the prefix characters in the trie from root to children as shown in execution_table steps 7-9.

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node if exists
- If missing, prefix not found
- After last char, collect all words below
- Words are nodes marked isWord
- Efficient for prefix-based word search

Full Transcript

This visualization shows how prefix search works using a trie data structure. We insert words by creating nodes for each character and marking the last node as a word end. To search a prefix, we start at the root and follow each character down the trie. If any character is missing, the prefix does not exist. Otherwise, after the last prefix character, we collect all words below by traversing child nodes marked as word ends. The execution table traces insertion of 'cat', 'car', and 'dog', then searches prefix 'ca' and collects 'cat' and 'car'. The variable tracker shows pointer positions and words found at each step. Key moments clarify why isWord is marked only at word ends, what happens if prefix chars are missing, and how word collection works. The quiz tests understanding of node creation, pointer positions during search, and prefix traversal.