Implement Radix Tree (Trie) in JavaScript

Radix trees, also known as prefix trees or tries, are specialized tree data structures that store a dynamic set of strings. They are particularly efficient for operations involving prefix matching, such as autocomplete suggestions or IP routing. Your challenge is to implement a Radix Tree in JavaScript.

Problem Description

You are tasked with creating a JavaScript class, RadixTree, that implements the core functionalities of a Radix Tree. This data structure will store strings and allow for efficient insertion, searching, and prefix-based searching.

Key Requirements:

1. Node Structure: Each node in the Radix Tree should represent a common prefix. Nodes should store:

   • An edge label (the portion of the string represented by the edge leading to this node).
   • A map or object to store child nodes, keyed by the first character of their respective edge labels.
   • A flag (e.g., isEndOfWord) to indicate if the path leading to this node represents a complete word inserted into the tree.

2. insert(word) method: This method should add a given word to the Radix Tree.

   • If the word already exists, no action is needed.
   • When inserting, you'll need to handle cases where:
     • The path for the word already exists.
     • The path for the word needs to be split to accommodate new words.
     • A new branch needs to be created.

3. search(word) method: This method should return true if the given word exists in the tree (i.e., it was previously inserted and isEndOfWord is true for its terminal node), and false otherwise.

4. startsWith(prefix) method: This method should return true if there is any word in the tree that starts with the given prefix, and false otherwise. This operation should be efficient.

Expected Behavior:

• The RadixTree should be initialized as an empty tree.
• Insertions should correctly build the tree structure.
• Searches should accurately determine the presence of exact words.
• startsWith operations should correctly identify prefixes.

Edge Cases to Consider:

• Inserting an empty string.
• Searching for an empty string.
• Inserting words that are prefixes of existing words, and vice versa.
• Inserting words that share longer common prefixes.
• Handling cases where an edge needs to be split.

Examples

Example 1: Basic Insertion and Search

const radixTree = new RadixTree();
radixTree.insert("apple");
radixTree.insert("apricot");
radixTree.insert("banana");

console.log(radixTree.search("apple"));     // Output: true
console.log(radixTree.search("app"));       // Output: false (it's a prefix, but not a full word)
console.log(radixTree.search("apricot"));   // Output: true
console.log(radixTree.search("band"));      // Output: false
console.log(radixTree.search("banana"));    // Output: true

Explanation: The words "apple", "apricot", and "banana" are inserted. "apple" and "apricot" share a common prefix "ap". "app" is a prefix of "apple", but "apple" was inserted as a complete word, so search("app") returns false.

Example 2: startsWith Operation

const radixTree = new RadixTree();
radixTree.insert("application");
radixTree.insert("apply");
radixTree.insert("apple");
radixTree.insert("banana");

console.log(radixTree.startsWith("app"));   // Output: true
console.log(radixTree.startsWith("appl"));  // Output: true
console.log(radixTree.startsWith("apple")); // Output: true
console.log(radixTree.startsWith("ban"));   // Output: true
console.log(radixTree.startsWith("ora"));   // Output: false
console.log(radixTree.startsWith("applica")); // Output: true
console.log(radixTree.startsWith("apricot")); // Output: false (no words start with this)

Explanation: Several words starting with "app" are inserted. startsWith("app") correctly identifies that "application", "apply", and "apple" all begin with this prefix.

Example 3: Edge Splitting Scenario

const radixTree = new RadixTree();
radixTree.insert("test");
console.log(radixTree.search("test")); // Output: true

radixTree.insert("tester");
console.log(radixTree.search("test"));   // Output: true (existing word still valid)
console.log(radixTree.search("tester")); // Output: true (new word inserted)

radixTree.insert("team");
console.log(radixTree.search("test"));   // Output: true
console.log(radixTree.search("tester")); // Output: true
console.log(radixTree.search("team"));   // Output: true
console.log(radixTree.startsWith("te")); // Output: true

Explanation: Initially, "test" is inserted. Then "tester" is inserted. The edge for "test" needs to be split. A new node for "er" will be created as a child of the "test" node. Subsequently, "team" is inserted, demonstrating a different branch from the root's "t" child.

Constraints

• The input word and prefix parameters for all methods will be strings.
• Words and prefixes will only contain lowercase English alphabet characters (a-z).
• The length of any given word or prefix will be between 0 and 100 characters, inclusive.
• The total number of words inserted into the tree will not exceed 10,000.
• Your implementation should aim for an efficient time complexity for insert, search, and startsWith operations, ideally logarithmic or linear with respect to the length of the strings involved.

Notes

• Consider how to represent the root of the tree.
• The core challenge lies in correctly handling the splitting and merging of edges when inserting new words.
• Think about the data structure for storing child nodes within a parent node. An object or a Map would be suitable.
• For startsWith, you'll traverse the tree based on the prefix and return true if you successfully reach the end of the prefix path within the tree.