Fixing the LeetCode 'Implement Trie (Prefix Tree)' bug: Python mutable default arguments leaking shared state

Debug a surprising LeetCode Trie failure: Python’s mutable default arguments share state across instances. Learn the None-sentinel fix for isolated tries.

LeetCode’s “Implement Trie (Prefix Tree)” looks routine until a trivial test starts failing. The runner asks for a fresh structure, calls startsWith on "a", and expects false. Instead, the result comes back true, and printing the structure shows data that clearly belongs to a prior test case. The trap is not in the trie logic itself, but in the constructor: a mutable default argument silently shares state across instances.

Bug trigger in code

The core logic of the trie is fine, but the initializer uses a shared dictionary as a default. That state bleeds across object creations and test cases.

from collections import deque

class PrefixTree:
    def __init__(self, branch_map = {}, label = '', terminal = False):
        self.branch_map = branch_map
        self.label = label
        self.terminal = terminal

    def __str__(self):
        s = ''
        s += self.label
        q = deque([])
        for ch in self.branch_map.values():
            q.append(ch)
        while q:
            n = q.popleft()
            s += n.label
            if n.terminal:
                s += 'T'
            for ch in n.branch_map.values():
                q.append(ch)
        return s

    def __repr__(self):
        return self.__str__()

    def child(self, val) -> "PrefixTree":
        return self.branch_map[val]

    def has(self, val) -> bool:
        return val in self.branch_map

    def mark(self) -> None:
        self.terminal = True

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if not node.has(ch):
                fresh = PrefixTree({}, ch, False)
                node.branch_map[ch] = fresh
            node = node.child(ch)
        node.mark()

    def search(self, word: str) -> bool:
        node = self
        for ch in word:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return node.terminal

    def startsWith(self, prefix: str) -> bool:
        # print(self)
        node = self
        for ch in prefix:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return True

What actually goes wrong

A minimal reproduction makes it obvious. Using a dict as a default parameter means every new instance without an explicit argument reuses the exact same dict.

class Holder:
    def __init__(self, payload={}):
        self.payload = payload
    def __repr__(self):
        return '{' + ','.join(f'{k}:{self.payload[k]}' for k in self.payload) + '}'
    def put(self, k, v):
        self.payload[k] = v

Try it interactively and you’ll see the carry-over between separate constructions:

>>> h1 = Holder()
>>> h1
{}
>>> h1.put(1, 2)
>>> h1
{1:2}
>>> h2 = Holder()
>>> h2
{1:2}

Every instance created without an explicit payload shares the same “initially {}” object, which is then mutated. The same thing happens with the trie’s children mapping. Insert in one place and the structure for other instances has already changed. That’s why a test that constructs a new Trie and calls startsWith can observe words like app and apple that belonged to an earlier run.

Rule of thumb: no mutable values as default parameter, unless you know what you are doing.

Fix and corrected code

The safe pattern is to default to None and create a fresh dictionary inside the initializer. That way each instance gets its own mapping.

class Holder:
    def __init__(self, payload=None):
        self.payload = {} if payload is None else payload
    def __repr__(self):
        return '{' + ','.join(f'{k}:{self.payload[k]}' for k in self.payload) + '}'
    def put(self, k, v):
        self.payload[k] = v

Applied to the trie:

from collections import deque

class PrefixTreeFixed:
    def __init__(self, branch_map=None, label='', terminal=False):
        self.branch_map = {} if branch_map is None else branch_map
        self.label = label
        self.terminal = terminal

    def __str__(self):
        s = ''
        s += self.label
        q = deque([])
        for ch in self.branch_map.values():
            q.append(ch)
        while q:
            n = q.popleft()
            s += n.label
            if n.terminal:
                s += 'T'
            for ch in n.branch_map.values():
                q.append(ch)
        return s

    def __repr__(self):
        return self.__str__()

    def child(self, val) -> "PrefixTreeFixed":
        return self.branch_map[val]

    def has(self, val) -> bool:
        return val in self.branch_map

    def mark(self) -> None:
        self.terminal = True

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if not node.has(ch):
                fresh = PrefixTreeFixed({}, ch, False)
                node.branch_map[ch] = fresh
            node = node.child(ch)
        node.mark()

    def search(self, word: str) -> bool:
        node = self
        for ch in word:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return node.terminal

    def startsWith(self, prefix: str) -> bool:
        node = self
        for ch in prefix:
            if not node.has(ch):
                return False
            node = node.child(ch)
        return True

Why this matters

Hidden shared state produces heisenbugs: a run in one mode looks fine, while another mode fails because earlier operations changed a supposedly empty structure. In environments that evaluate multiple cases in sequence, that leakage surfaces as inconsistent results and confusing prints that reveal data from prior tests. Using a fresh mapping per instance restores isolation and makes the outcome deterministic.

Takeaways

If you see inexplicable cross-test contamination with classes that accept containers in their constructor, check for mutable default arguments. Replace them with a None sentinel and allocate new objects inside the initializer. This small change prevents state from propagating between instances, keeps data structures independent, and avoids false positives like startsWith returning true when no insert ever happened in that test.