Description

A trie, is a Tree like DS, which uses a dict for the children.
root =

Reach for when

You need to compare two strings

Runtime

lookup: O(log(n))
insert: O(n)

Visualization

Pseudocode

Traverse the tree, if a node does not exist add it.

Code

trie = {}

def insert(word):
    node = trie
    for ch in word:
        if ch not in node:
            node[ch] = {}
        node = node[ch]

def has_prefix(prefix):
    node = trie
    for ch in prefix:
        if ch not in node:
            return False
        node = node[ch]
    return True