Trie Data Structure

Background

Tries are used in autocomplete systems, spell checkers, IP routing tables, and dictionary implementations.

Problem

Create a Trie class supporting insert(word), search(word), and startsWith(prefix) operations for efficient string storage and lookup.

Input

No input; the Trie is initialized empty and words are added via insert.

Output

A Trie instance with insert, search, and startsWith methods.

Sample tests

Input: insert("apple"), search("apple"), startsWith("app")

Expected: true, true

Your solution

Learning objective

Understand tree-based data structures for string operations and prefix matching.