This change from _EMPTY to _SENTINEL should be a separate PR since it’s unrelated to types.

Similarly, why is this changed from None to empty string?

first, the type of path assigned to List[str] as all of _Node.iterate method'call passed list(xxx) in path. Append None to path would raise type-check error.

second, in these codes

if (not shallow or node.value is _SENTINEL) and node.children:
    stack.append(iter(items(node.children)))
    path.append(None)

while True:
    try:
        step, node = next(stack[-1])
        path[-1] = step
        break
    except StopIteration:
        stack.pop()
        path.pop()
    except IndexError:
        return

you can see that if path does have a new value appended, it will eventually be replaced by step or be popped.

Hmm, actually empty string isn’t actually correct anyway. What path is can be overridden by subclassess if they decide to overload _path_from_key. The only requirement Trie class has is that each element of the path (what is called step in the documentation) is hashable.

So path passed to the function is a List[T]. Since the method doesn’t know what T is, it treats the list as List[Optional[T]] and uses None value.

I think _Node might need to be a generic type over S and V where S is a type which depends on how _path_from_key is defined. I’m not really sure what the best approach is.