Trie Search Operation in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths down the tree represent words.

beginner

What does the search operation in a Trie do?

The search operation checks if a given word exists in the Trie by following nodes corresponding to each character of the word. If all characters are found and the last node marks the end of a word, the search returns true.

beginner

In Trie search, what does it mean if a character node is missing during traversal?

If a character node is missing while traversing the Trie for a word, it means the word does not exist in the Trie, so the search returns false.

intermediate

Why do we check the 'end of word' flag in the last node during Trie search?

Because some words can be prefixes of others, the 'end of word' flag confirms that the path corresponds to a complete word stored in the Trie, not just a prefix.

intermediate

What is the time complexity of searching a word in a Trie?

The time complexity is O(m), where m is the length of the word being searched, because the search visits one node per character.

What does the Trie search operation return if the word is not found?

A undefined

B true

C null

D false

If the word is not found in the Trie, the search operation returns false.

During Trie search, what happens if a character node is missing?

A Continue searching next character

B Return false immediately

C Mark word as found

D Restart search from root

If a character node is missing, the word cannot be in the Trie, so search returns false immediately.

What does the 'end of word' flag indicate in a Trie node?

A Word ends at this node

B Node is root

C Node has children

D Node is empty

The 'end of word' flag marks that a complete word ends at this node.

What is the main advantage of using a Trie for search?

A Faster than hash tables for all operations

B Automatically sorts words

C Search time depends on word length, not number of words

D Uses less memory than arrays

Trie search time depends on the length of the word, not the total number of words stored.

If the word 'cat' is stored in a Trie, which nodes are visited during search?

A c -> a -> t

B c -> t -> a

C a -> c -> t

D t -> a -> c

The search visits nodes in the order of the word's characters: c, then a, then t.

Explain step-by-step how the Trie search operation works for the word 'dog'.

Think about checking each character one by one and the end of word flag.

Why is the 'end of word' flag important in Trie search, especially when words share prefixes?

Consider the difference between 'cat' and 'caterpillar'.