Skip to main content
CodeEasy v0.1

Implement Trie (Prefix Tree)

Medium Subject: Tries
Time Complexity
O(L)
Space Complexity
O(L)

Problem Description

Problem Statement

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class with insert, search, and startsWith methods.

Example 1:

  • Input: ["Trie","insert","search","search","startsWith","insert","search"]\n[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
  • Output: [null,null,true,false,true,null,true]

Optimal Solution

Python

Approach: Nested Hash Maps

Each Trie node contains a dictionary of children and a boolean flag indicating if it's the end of a word. Insert creates paths. Search verifies the full path and end flag. StartsWith verifies the path exists.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True