Definition

Trie is a search tree data structure mainly used for storing and retrieving strings from an array or dictionary.

Node Structure

children - The children (letters) the node has, dictionary where {value: TrieNode}
isTerminal - bool flag indicating the end of a branch (word)

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.isTerminal = False

Operations

Insertion - Add a word to the tree, EG: apple
Search - Search for a word (isTerminal=True)
Prefix search - Search for the word starting from prefix (isTerminal doesnt matter)
Deletion - Delete word from the tree, by changing isTerminal from True to False, optionally can prune as well.

Trie code with operations

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.isTerminal = False

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

    def insertion(self, word: str) -> None:
        curr = self.root

        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        
        curr.isTerminal = True

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

        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]

        return curr.isTerminal

    def searchPrefix(self, prefix: str) -> bool:
        curr = self.root

        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]

        return True

    def deletion(self, word: str) -> bool:
        found = False

        def _del(node, i):
            nonlocal found

            if i == len(word):
                if not node.isTerminal:
                    return False
                node.isTerminal = False
                found = True
                return len(node.children) == 0

            ch = word[i]
            if ch not in node.children:
                return False

            should_prune = _del(node.children[ch], i + 1)

            if should_prune:
                del node.children[ch]

            return (not node.isTerminal) and (len(node.children) == 0)

        _del(self.root, 0)
        return found

Time and Space Complexity for the Operations

Function	Time Complexity	Space Complexity
`insertion(word)`	O(L)	O(L) (new nodes worst case)
`search(word)`	O(L)	O(1)
`searchPrefix(prefix)`	O(L)	O(1)
`deletion(word)`	O(L)	O(L) (recursion stack)

Blog

2025