Build a Trie for AutocompleteStep 4 of 5

Delete with Pruning

12345

Step 4: Delete with Pruning

Removing a word is more than flipping is_word off. You should also prune nodes that are no longer part of any word, so the tree doesn't accumulate dead branches.

  • delete(word): if the word isn't present, return False. Otherwise unmark it and remove any now-empty, non-word nodes on the way back up; return True.

A node can be pruned only if it has no children and isn't itself the end of another word. Shared prefixes must survive: deleting "car" must not break "care".

Hints
Starter code
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._find(prefix) is not None

    def delete(self, word):
        """Remove a word and prune dead nodes. Return True if it was present."""
        if not self.search(word):
            return False

        def _prune(node, i):
            # returns True if this node can be removed by its parent
            if i == len(word):
                node.is_word = False
            else:
                ch = word[i]
                # TODO: recurse into node.children[ch]; if it reports it can be
                # pruned, delete it from node.children.
                pass
            return (not node.is_word) and len(node.children) == 0

        _prune(self.root, 0)
        return True
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step