🟨 Implement Trie (Prefix Tree) (#208)

🔗 Problem Link

• LeetCode - Implement Trie
• NeetCode - Implement Trie

📋 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. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

• Trie() Initializes the trie object.
• void insert(String word) Inserts the string word into the trie.
• boolean search(String word) Returns true if the string word is in the trie, and false otherwise.
• boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

💡 Examples

Example 1

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

🔑 Key Insights & Approach

Core Observation: Each node has children for each character (a-z) and a flag for word end.

Why Trie?

• Insert: O(m) where m = word length
• Search: O(m)
• Prefix search: O(m)
• Space: O(ALPHABET_SIZE * N * M) worst case

Approaches:

1. Array-based children: O(1) child lookup, more space
2. HashMap-based children: O(1) avg lookup, less space

Pattern: "Trie Data Structure" for prefix operations.

🐍 Solution: Python

Approach: HashMap-based Children

Time Complexity: O(m) per operation | Space Complexity: O(N * M)

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

Approach 2: Array-based (26 letters)

Time Complexity: O(m) per operation | Space Complexity: O(26 * N * M)

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

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

    def _char_to_index(self, char):
        return ord(char) - ord('a')

    def insert(self, word: str) -> None:
        node = self.root

        for char in word:
            idx = self._char_to_index(char)
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]

        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root

        for char in word:
            idx = self._char_to_index(char)
            if not node.children[idx]:
                return False
            node = node.children[idx]

        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root

        for char in prefix:
            idx = self._char_to_index(char)
            if not node.children[idx]:
                return False
            node = node.children[idx]

        return True

🔵 Solution: Golang

Approach: Map-based Children

Time Complexity: O(m) per operation | Space Complexity: O(N * M)

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
            isEnd:    false,
        },
    }
}

func (this *Trie) Insert(word string) {
    node := this.root

    for _, char := range word {
        if _, exists := node.children[char]; !exists {
            node.children[char] = &TrieNode{
                children: make(map[rune]*TrieNode),
                isEnd:    false,
            }
        }
        node = node.children[char]
    }

    node.isEnd = true
}

func (this *Trie) Search(word string) bool {
    node := this.root

    for _, char := range word {
        if _, exists := node.children[char]; !exists {
            return false
        }
        node = node.children[char]
    }

    return node.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this.root

    for _, char := range prefix {
        if _, exists := node.children[char]; !exists {
            return false
        }
        node = node.children[char]
    }

    return true
}

📚 References

• NeetCode - Implement Trie