Prefix Search Using Trie in DSA Java - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each character in prefix

↓

Check if child node for character exists?

No→Prefix not found

Yes↓

Move to child node

↓

Repeat for next character

↓

All prefix chars found

↓

Collect all words from this node

↓

Return list of words with prefix

Start from the root and follow nodes for each prefix character. If all characters exist, collect all words below that node.

Execution Sample

DSA Java

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
List<String> res = trie.searchPrefix("ca");
System.out.println(res);

Insert words 'cat', 'car', 'dog' into trie, then search for words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t (end)	root.children['c'] created c.children['a'] created a.children['t'] created	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t (end), a -> r (end)	a.children['r'] created	root └─ c └─ a ├─ t* └─ r*
3	Insert 'dog'	root -> c -> a -> t (end), a -> r (end), root -> d -> o -> g (end)	root.children['d'] created d.children['o'] created o.children['g'] created	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
4	Search prefix 'ca' - check 'c'	No change	Move pointer from root to c	Pointer at node 'c'
5	Search prefix 'ca' - check 'a'	No change	Move pointer from c to a	Pointer at node 'a'
6	Collect words from node 'a'	No change	Traverse subtree from 'a' to find words	Words found: ['cat', 'car']
7	Return result	No change	Return list ['cat', 'car']	Output: ['cat', 'car']
8	Search prefix 'do' - check 'd'	No change	Move pointer from root to d	Pointer at node 'd'
9	Search prefix 'do' - check 'o'	No change	Move pointer from d to o	Pointer at node 'o'
10	Collect words from node 'o'	No change	Traverse subtree from 'o' to find words	Words found: ['dog']
11	Return result	No change	Return list ['dog']	Output: ['dog']
12	Search prefix 'z' - check 'z'	No change	No child 'z' at root	Prefix not found, return []

💡 Search stops when prefix character not found or all prefix characters processed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 10	Final
Trie root	empty	root with 'c'	root with 'c'	root with 'c' and 'd'	same	same	same
Pointer	root	root	root	root	node 'a'	node 'o'	root
Words collected	[]	[]	[]	[]	['cat', 'car']	['dog']	[]

Key Moments - 3 Insights

Why do we stop searching if a prefix character node does not exist?

Because the prefix cannot be formed if any character node is missing. See execution_table step 12 where 'z' is missing at root, so search ends with empty result.

How do we collect all words after finding the prefix node?

We traverse all child nodes recursively from the prefix node to find complete words. See execution_table steps 6 and 10 where subtree traversal collects 'cat', 'car' and 'dog'.

Why do we mark nodes as 'end' of word?

To know which nodes represent complete words. Without this, we can't distinguish 'car' from 'carpet'. See visual state with '*' marking word ends in steps 1-3.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, where is the pointer located?

A At node 'a'

B At root node

C At node 'c'

D At node 't'

💡 Hint

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

At which step does the trie first contain the word 'dog'?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at 'Operation' and 'Nodes in Trie' columns to see when 'dog' is inserted.

If we search prefix 'ca' but 'a' node was missing, what would happen?

A Return words starting with 'c'

B Return all words in trie

C Return empty list immediately

D Throw an error

💡 Hint

Refer to step 12 where missing prefix character causes immediate empty result.

Concept Snapshot

Trie stores words by characters in nodes.
Insert: create nodes for each char.
Search prefix: follow nodes for prefix chars.
If prefix found, collect all words below.
Nodes marked as word end to identify complete words.

Full Transcript

We start with an empty trie root node. When inserting 'cat', nodes for 'c', 'a', and 't' are created, marking 't' as end of word. Next, inserting 'car' adds a sibling node 'r' under 'a'. Inserting 'dog' creates a new branch from root with nodes 'd', 'o', 'g'. To search prefix 'ca', we move pointer from root to 'c', then to 'a'. From 'a', we collect all words below, which are 'cat' and 'car'. Searching prefix 'do' moves pointer to 'd' then 'o', collecting 'dog'. Searching prefix 'z' fails immediately as 'z' node does not exist at root, returning empty list. This process shows how trie efficiently supports prefix search by traversing nodes and collecting words below the prefix node.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand what prefix search means

   Prefix search means finding all words that start with a certain beginning sequence of letters.

2. Step 2: Understand Trie's role in prefix search

   A Trie stores words in a tree where each node represents a letter, making it easy to find all words sharing the same prefix by traversing the tree.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Prefix search = efficient word lookup [OK]

Hint: Trie nodes represent letters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structures
• Thinking Trie is for arithmetic operations
• Assuming Trie stores numbers only

2. Which of the following is the correct way to declare a Trie node class in Java?

easy

A. class TrieNode { int[] children = new int[26]; boolean isEndOfWord; }

B. class TrieNode { char[] children = new char[26]; boolean isEndOfWord; }

C. class TrieNode { String[] children = new String[26]; boolean isEndOfWord; }

D. class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord; }

Solution

1. Step 1: Identify the correct type for children nodes

   Each child should be a reference to another TrieNode, so the array type must be TrieNode[].

2. Step 2: Check the other parts of the class

   Boolean isEndOfWord marks if the node ends a word, which is correct in class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord; }.

3. Final Answer:

   class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord; } -> Option D

4. Quick Check:

   Children are TrieNode references [OK]

Hint: Children array holds TrieNode references, not primitives [OK]

Common Mistakes:

• Using int or char arrays instead of TrieNode array
• Using String array for children
• Forgetting to mark end of word

3. Given the following code snippet, what will be the output?

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
System.out.println(trie.startsWith("ca"));
System.out.println(trie.startsWith("do"));
System.out.println(trie.startsWith("bat"));

medium

A. true
true
false

B. true
false
false

C. false
true
false

D. false
false
true

Solution

1. Step 1: Insert words into the Trie

   Words "cat", "car", and "dog" are inserted, so prefixes "ca" and "do" exist in the Trie.

2. Step 2: Check startsWith results

   startsWith("ca") returns true because "cat" and "car" start with "ca".
   startsWith("do") returns true because "dog" starts with "do".
   startsWith("bat") returns false because no word starts with "bat".

3. Final Answer:

   true true false -> Option A

4. Quick Check:

   Prefix "ca" and "do" found, "bat" not found [OK]

Hint: Check inserted words' prefixes carefully [OK]

Common Mistakes:

• Assuming startsWith returns false if word not complete
• Confusing startsWith with search for whole word
• Mixing up true/false outputs

4. The following Java method is intended to check if a prefix exists in a Trie, but it has a bug. What is the bug?

public boolean startsWith(String prefix) {
    TrieNode node = root;
    for (int i = 0; i <= prefix.length(); i++) {
        char c = prefix.charAt(i);
        if (node.children[c - 'a'] == null) return false;
        node = node.children[c - 'a'];
    }
    return true;
}

medium

A. The root node is not initialized before the loop

B. The loop condition should be < instead of <= to avoid IndexOutOfBoundsException

C. The method should return false at the end instead of true

D. The character indexing is wrong; should use c + 'a'

Solution

1. Step 1: Analyze the for-loop condition

   The loop runs from i = 0 to i <= prefix.length(), which means it tries to access prefix.charAt(prefix.length()), causing an IndexOutOfBoundsException.

2. Step 2: Correct the loop condition

   The loop should run while i < prefix.length() to access valid characters only.

3. Final Answer:

   The loop condition should be < instead of <= to avoid IndexOutOfBoundsException -> Option B

4. Quick Check:

   Loop index must be less than length [OK]

Hint: Loop index must be less than string length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Incorrect character arithmetic
• Returning wrong boolean at the end

5. You want to find all words in a Trie that start with the prefix "app". Which approach correctly retrieves all such words?

hard

A. Use a hash map to store all words and filter those starting with "app"

B. Search each word in the Trie individually to check if it starts with "app"

C. Traverse the Trie to the node representing 'p' in "app", then perform a depth-first search collecting all words below

D. Insert "app" as a word and then search for it

Solution

1. Step 1: Locate the prefix node in the Trie

   Traverse the Trie following letters 'a', 'p', 'p' to reach the node representing the last 'p' in "app".

2. Step 2: Collect all words below this node

   Perform a depth-first search (DFS) from this node to find all complete words that start with "app".

3. Final Answer:

   Traverse the Trie to the node representing 'p' in "app", then perform a depth-first search collecting all words below -> Option C

4. Quick Check:

   Prefix node + DFS = all matching words [OK]

Hint: Find prefix node, then DFS to collect words [OK]

Common Mistakes:

• Checking all words instead of using Trie structure
• Using hash map instead of Trie traversal
• Confusing insertion with search