Prefix search & autocomplete

Prefix search means answering 'which stored strings start with this prefix?'. In a trie, every word that starts with a prefix lives in the subtree under the prefix's last node, so the search has two phases: walk down the prefix in O(P) steps, then collect results from that subtree only.

Autocomplete is prefix search with a limit and an order: return the top k suggestions, either alphabetically or by popularity. Alphabetical order comes for free from a pre-order DFS that visits children in sorted order. Popularity order needs extra data, such as a frequency on each word, or a precomputed list of the best k words cached on every node.

1. 1Build the trie from the dictionary. Store the full word (and its frequency if ranking matters) on its end node, so you do not have to rebuild the string during the DFS.
2. 2For a query prefix, walk from the root one character at a time. If a character is missing, no word has this prefix: return an empty list.
3. 3From the prefix node, run a DFS. Visit the node itself first (pre-order) and add its word if it ends one; then visit children in sorted character order. This yields words in alphabetical order.
4. 4Stop the DFS as soon as you have k results, so the cost is bounded by the size of the part of the subtree you actually touch, not the whole dictionary.
5. 5For popularity ranking at scale, precompute at each node the top k words in its subtree (by frequency). A query then becomes 'walk the prefix and return the cached list' in O(P + k) time, at the cost of extra memory and work on updates.

class Node:
    def __init__(self):
        self.children = {}
        self.word = None      # the full word, stored at its last node

def build(words):
    root = Node()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, Node())
        node.word = w
    return root

def suggest(root, prefix, k=3):
    node = root
    for ch in prefix:                 # 1. walk down to the prefix node
        node = node.children.get(ch)
        if node is None:
            return []
    out = []
    def dfs(n):                       # 2. pre-order DFS = alphabetical order
        if len(out) == k:
            return
        if n.word is not None:
            out.append(n.word)
        for ch in sorted(n.children):
            dfs(n.children[ch])
    dfs(node)
    return out

build stores each full word on its end node. suggest walks to the prefix node, then runs a pre-order DFS with sorted children, which yields alphabetical order, and stops at k results. Time is O(P) for the walk plus the nodes visited until k words are found.

Cost: Walk O(P) for a prefix of length P. DFS collection is bounded by the nodes visited before finding k words (worst case the whole subtree). With cached top-k lists per node a query is O(P + k), but memory grows by k entries per node.