Trie Node Design and Initialization in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie Node in a Trie data structure?

A Trie Node is a building block of a Trie. It stores links to child nodes for each character and a flag to mark if it ends a word.

beginner

How do you initialize the children of a Trie Node in TypeScript?

You initialize children as an object or map where keys are characters and values are Trie Nodes, starting empty.

beginner

What property in a Trie Node indicates the end of a word?

A boolean property, often named 'isEndOfWord', marks if the node completes a valid word.

beginner

Show a simple TypeScript class snippet for a Trie Node with children and end flag.

class TrieNode {
  children: { [key: string]: TrieNode } = {};
  isEndOfWord: boolean = false;
}

intermediate

Why do we use an object or map for children in a Trie Node instead of an array?

Because children represent characters which are keys, using an object/map allows quick lookup by character without wasting space.

What does the 'isEndOfWord' property in a Trie Node represent?

A Marks the node as the end of a valid word

B Counts the number of children nodes

C Stores the character of the node

D Indicates if the node has any children

The 'isEndOfWord' boolean marks if the node completes a valid word in the Trie.

How are children nodes typically stored in a Trie Node in TypeScript?

A As an object with characters as keys and Trie Nodes as values

B As a simple string

C As a number array

D As a boolean flag

Children are stored as an object mapping characters to Trie Nodes for quick access.

Which of these is NOT a typical property of a Trie Node?

A children

B isEndOfWord

C parentNode

D character

While some implementations may track parent nodes, it is not a typical required property.

What is the initial value of 'isEndOfWord' when a Trie Node is created?

A true

B false

C null

D undefined

'isEndOfWord' starts as false because the node does not represent the end of a word initially.

Why is an object preferred over an array for children in a Trie Node?

A Arrays cannot store nodes

B Arrays are slower to access

C Objects use less memory always

D Because characters are keys, not indexes

Characters are keys, so an object allows direct access by character instead of numeric index.

Describe how you would design and initialize a Trie Node in TypeScript.

Think about what data each node needs to store for the Trie to work.

Explain why the children property in a Trie Node is an object instead of an array.

Consider how you find the next node for a given character.