Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python trie deletion: remove one word without losing its prefix neighbors

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

Trie deletion removes a word’s terminal marker and prunes only branches that no longer lead to any retained word.

Download Python source kit

Operation contract

The route-label trie stores bounded uppercase ASCII words. Removing DEL unmarks its terminal node but preserves DELHI beneath it. Removing the last descendant later can prune that branch completely. A missing word returns false and leaves the trie unchanged. The caller owns the constructed trie; received arbitrary nested dictionaries are not accepted tree input.

Failure and ownership boundary

A prefix can be a complete word and an ancestor of another word at the same time. Deleting every visited node would lose valid neighbors. This fixture has no concurrent readers or compressed edges. Python trie: exact words, prefixes and node allocation and Python variables: names refer to objects, assignment does not copy explain the ownership and read-side boundaries.

Working program

python
import re

def valid_word(word):
    return isinstance(word, str) and re.fullmatch(r"[A-Z]{1,32}", word) is not None

def build_routes(words):
    if len(words) > 128 or any(not valid_word(word) for word in words):
        raise ValueError("route word budget rejected")
    root = {"terminal": False, "children": {}}
    for word in words:
        node = root
        for symbol in word:
            node = node["children"].setdefault(symbol, {"terminal": False, "children": {}})
        node["terminal"] = True
    return root

def remove_route(root, word):
    if not valid_word(word):
        raise ValueError("route word rejected")
    node = root; path = []
    for symbol in word:
        if symbol not in node["children"]:
            return False
        path.append((node, symbol)); node = node["children"][symbol]
    if not node["terminal"]:
        return False
    node["terminal"] = False
    for parent, symbol in reversed(path):
        child = parent["children"][symbol]
        if child["terminal"] or child["children"]:
            break
        del parent["children"][symbol]
    return True

def route_words(root):
    result = []
    def visit(node, prefix):
        if node["terminal"]:
            result.append(prefix)
        for symbol, child in sorted(node["children"].items()):
            visit(child, prefix + symbol)
    visit(root, "")
    return result

routes = build_routes(["DEL", "DELHI", "BOM"])
print(remove_route(routes, "DEL"), route_words(routes))
print(remove_route(routes, "DEL"), route_words(routes))
print(remove_route(routes, "DELHI"), route_words(routes))

Output

Output
True ['BOM', 'DELHI']
False ['BOM', 'DELHI']
True ['BOM']

Costs and limits

Deletion visits at most the word’s L symbols and retains O(L) parent references. Complete ordered listing has output-dependent work, sorting and string-construction costs. The trie retains nodes proportional to stored prefixes, not merely the number of words.

Common Mistakes

  • A terminal prefix can have valid descendants.
  • Prune only nonterminal nodes with no retained children.

Connected lessons

Python trie: exact words, prefixes and node allocation, Python variables: names refer to objects, assignment does not copy, Python recursion: bound depth instead of raising the limit.

Check the next state boundary

Python compressed trie: merge single-child paths without losing terminal words.

Follow the ownership and update boundary

Python compressed trie updates: split on insertion and compact after deletion.

python
trie-deletion
Storage details