Implement a Trie Data Structure in JavaScript

This challenge requires you to build a Trie (prefix tree) data structure from scratch in JavaScript. A Trie is an efficient tree-like data structure used for storing and searching strings. It's particularly useful for applications like autocomplete, spell checkers, and dictionary implementations where prefix-based searches are common.

Problem Description

You need to implement a Trie class in JavaScript. This class should support the following operations:

1. insert(word): Adds a word to the Trie.
2. search(word): Returns true if the word exists in the Trie, and false otherwise.
3. startsWith(prefix): Returns true if there is any word in the Trie that starts with the given prefix, and false otherwise.

Key Requirements:

• Each node in the Trie should represent a character.
• A node should have a way to store its children (representing the next characters in a word). A JavaScript object (or Map) is a suitable choice for this.
• A mechanism is needed to mark the end of a word. This can be a boolean flag on a node.

Expected Behavior:

• insert operations should build the Trie correctly.
• search should accurately identify complete words that have been inserted.
• startsWith should correctly identify if any inserted word begins with the given prefix.

Edge Cases to Consider:

• Inserting an empty string.
• Searching for an empty string.
• Searching for a prefix that is also a complete word.
• Inserting duplicate words.
• Words that are prefixes of other words.

Examples

Example 1:

Input:
trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app");   // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");   // returns true

Output:

true
false
true
true

Explanation: Initially, the Trie is empty. After trie.insert("apple"): The Trie contains the path for "apple". trie.search("apple") returns true because "apple" is a complete word. trie.search("app") returns false because "app" was not explicitly inserted as a word. trie.startsWith("app") returns true because "apple" starts with "app". After trie.insert("app"): The Trie now marks "app" as a complete word. trie.search("app") now returns true.

Example 2:

Input:
trie = new Trie();
trie.insert("banana");
trie.insert("band");
trie.startsWith("ban"); // returns true
trie.startsWith("banda"); // returns false
trie.search("ban"); // returns false
trie.search("band"); // returns true

Output:

true
false
false
true

Explanation: trie.startsWith("ban") returns true because both "banana" and "band" start with "ban". trie.startsWith("banda") returns false because no word in the Trie starts with "banda". trie.search("ban") returns false as "ban" was not inserted as a word. trie.search("band") returns true as "band" was inserted.

Example 3 (Edge Case):

Input:
trie = new Trie();
trie.insert(""); // Inserting an empty string
trie.search(""); // returns true
trie.startsWith(""); // returns true
trie.insert("a");
trie.search(""); // returns true (empty string remains inserted)
trie.startsWith("a"); // returns true

Output:

true
true
true
true

Explanation: The Trie can handle empty strings. insert("") marks the root node as the end of a word. search("") and startsWith("") should return true if the empty string has been inserted.

Constraints

• Words will consist of lowercase English letters ('a'-'z').
• The number of words inserted will be between 0 and 1000.
• The length of each word will be between 0 and 50 characters.
• The length of prefixes for startsWith and words for search will be between 0 and 50 characters.
• The time complexity for insert, search, and startsWith operations should ideally be O(L), where L is the length of the word or prefix.

Notes

• Consider how you will represent the Trie nodes. A simple object where keys are characters and values are child nodes is a common approach.
• Remember to have a way to signify if a node marks the end of a valid word.
• Think about the base case for recursion or iteration when traversing the Trie.