Implement Trie (Prefix Tree)

Google Interview Question

Problem Overview

Difficulty: Medium
LeetCode Pattern: Trie

Build a Trie (prefix tree) that supports 3 operations:

1. insert(word)

   1. Store the word in the Trie.

2. search(word)

   1. Return True if the exact word exists.

   2. Return False otherwise.

3. startsWith(prefix)

   1. Return True if any word in the Trie starts with the given prefix.

   2. Return False otherwise.

Example
trie = Trie()

trie.…