179. Implement Trie

Why this mechanism works

Each edge consumes one character, so a root-to-node path identifies a prefix. A separate terminal flag distinguishes a complete inserted word from a prefix of a longer word. Search and prefix lookup share traversal; only exact search needs the terminal check.

State and boundaries

Each node has a children dictionary and terminal flag. The current node represents all characters consumed so far.

Protocol

1. Start at the root.
2. During insertion create missing character edges.
3. Mark the final node terminal.
4. During lookup fail on a missing edge.
5. For exact search require terminal; for prefix search require only a reached node.

Visualization

root - a - p - p - l - e*
prefix 'app': path exists
word 'app': false until its node is marked *

Python implementation

from structures import run_operations

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

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

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.terminal = True

    def _walk(self, text):
        node = self.root
        for char in text:
            node = node.children.get(char)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.terminal

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 __init__: self.children = {}
self=TrieNode{'children':{}}

L6 __init__: self.terminal = False
self=TrieNode{'children':{}, 'terminal':False}

L10 __init__: self.root = TrieNode()
self=Trie{'root':TrieNode...}

L13 insert: node = self.root
self=Trie{'root':TrieNode...}; word='apple'; node=TrieNode{'children':{}, 'terminal':False}

L14 insert: for char in word:
self=Trie{'root':TrieNode...}; word='apple'; node=TrieNode{'children':{}, 'terminal':False}; char='a'

L5 __init__: self.children = {}
self=TrieNode{'children':{}}

L6 __init__: self.terminal = False
self=TrieNode{'children':{}, 'terminal':False}

L16 insert: node.children[char] = TrieNode()
self=Trie{'root':TrieNode...}; word='apple'; node=TrieNode{'children':{...:...}, 'terminal':False}; char='a'

... 34 intermediate state changes omitted ...

L22 _walk: for char in text:
self=Trie{'root':TrieNode...}; text='app'; node=TrieNode{'children':{...:...}, 'terminal':False}; char='a'

L22 _walk: for char in text:
self=Trie{'root':TrieNode...}; text='app'; node=TrieNode{'children':{...:...}, 'terminal':False}; char='p'

L23 _walk: node = node.children.get(char)
self=Trie{'root':TrieNode...}; text='app'; node=TrieNode{'children':{...:...}, 'terminal':True}; char='p'

L29 search: node = self._walk(word)
self=Trie{'root':TrieNode...}; word='app'; node=TrieNode{'children':{...:...}, 'terminal':True}

L5 __init__: self.children = {}
self=TrieNode{'children':{}}

L6 __init__: self.terminal = False
self=TrieNode{'children':{}, 'terminal':False}

L10 __init__: self.root = TrieNode()
self=Trie{'root':TrieNode...}

L21 _walk: node = self.root
self=Trie{'root':TrieNode...}; text=''; node=TrieNode{'children':{}, 'terminal':False}

L33 startsWith: return self._walk(prefix) is not None
self=Trie{'root':TrieNode...}; prefix=''

L21 _walk: node = self.root
self=Trie{'root':TrieNode...}; text=''; node=TrieNode{'children':{}, 'terminal':False}

L29 search: node = self._walk(word)
self=Trie{'root':TrieNode...}; word=''; node=TrieNode{'children':{}, 'terminal':False}

L13 insert: node = self.root
self=Trie{'root':TrieNode...}; word=''; node=TrieNode{'children':{}, 'terminal':False}

L18 insert: node.terminal = True
self=Trie{'root':TrieNode...}; word=''; node=TrieNode{'children':{}, 'terminal':True}

L21 _walk: node = self.root
self=Trie{'root':TrieNode...}; text=''; node=TrieNode{'children':{}, 'terminal':True}

L29 search: node = self._walk(word)
self=Trie{'root':TrieNode...}; word=''; node=TrieNode{'children':{}, 'terminal':True}

Why the solution is correct

Insertion creates exactly the path spelling the word and marks its endpoint. Lookup follows that unique character path, so a reached node proves prefix existence; its terminal flag proves exact insertion. Each edge consumes a character, bounding all operations by input length.

Time and space

Expected O(L) time per length-L operation with dictionary edges. O(S) stored nodes/edges for total inserted characters S, plus the root; lookup uses O(1) auxiliary state.

Common mistakes

Treating every reached node as a word makes search('app') succeed after inserting only 'apple'. Using a character as a terminal sentinel can collide with valid input; a separate flag avoids that.

Reasoning card

Transfer exercise

Add deletion without removing nodes still needed by another word or prefix.