Implement Trie (Prefix Tree)

Trie
Medium

Approach

Diagrams

Analysis

Time

Space

from collections import defaultdict


class TrieNode:
    def __init__(self, val=None):
        self.val = val
        self.children = defaultdict(TrieNode)
        self.tail = 0


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

    def insert(self, word):
        node = self.root

        for letter in word:
            if letter not in node.children:
                node.children[letter] = TrieNode(letter)

            node = node.children[letter]

        node.tail += 1

    def search(self, word):
        node = self.root

        for letter in word:
            node = node.children.get(letter)

            if node is None:
                return False

        return node.tail > 0

    def startsWith(self, prefix):
        node = self.root

        for letter in prefix:
            node = node.children.get(letter)

            if node is None:
                return False

        return True

Learn

#Trie

Videos