Trie Insert Operation in DSA Javascript - 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 insert operation do in a Trie?

The insert operation adds a word to the Trie by creating nodes for each character if they don't exist and marking the end of the word.

beginner

In Trie insertion, what does marking the end of a word mean?

It means setting a flag (like isEndOfWord) on the last node of the inserted word to indicate that a complete word ends there.

intermediate

Why do we create new nodes only if the character does not exist in the current Trie node during insertion?

Because existing nodes represent prefixes already stored, so we reuse them to save space and only add new nodes for new characters.

intermediate

What is the time complexity of inserting a word of length n into a Trie?

The time complexity is O(n), where n is the length of the word, because we process each character once.

What does each node in a Trie typically represent?

A A sentence

B A character of a word

C A number

D A whole word

Each node in a Trie represents a single character of a word.

During insertion, if a character node already exists, what should the algorithm do?

A Reuse the existing node and move to it

B Create a new node anyway

C Delete the existing node

D Stop insertion

If the node exists, reuse it to continue inserting the next character.

What flag is commonly used to mark the end of a word in a Trie node?

A isWordStart

B isLeafNode

C isEndOfWord

D isRoot

The isEndOfWord flag marks the node as the end of a valid word.

What is the main advantage of using a Trie for storing words?

A Stores numbers efficiently

B Uses less memory than arrays

C Sorts words automatically

D Faster insertion and search by prefix

Tries allow fast insertion and search especially for prefix-based queries.

If you insert the word 'cat' and then 'car', how many new nodes are created for 'car'?

A 1

B 2

C 3

D 0

Only the last character 'r' node is new; 'c' and 'a' nodes already exist from 'cat'.

Explain step-by-step how to insert the word 'dog' into an empty Trie.

Think about creating nodes for each character and marking the last one.

Describe why Tries are efficient for prefix searches and how insertion supports this.

Focus on shared prefixes and node reuse.