Implement Trie (Prefix Tree)

doordash Problem Description Implement a Trie (Prefix Tree) with the following operations: insert(word): Inserts a word into the trie. search(word): Returns whether the word is in the trie. startsWith(prefix): Returns whether there is any word in the trie that starts with the given prefix. Input Operations are performed in the same program. Output The search operations return a boolean indicating success or failure. Example Trie 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 Example Input insert apple search apple