Lesson 07 · Listing every word in order - Build an Autocomplete Engine

Listing every word in order

To collect completions you first need to walk a subtree and gather the words in it. Today you build that depth-first collection and prove it returns words in deterministic lexicographic order by visiting child characters sorted.

The goal

Return every stored word by a depth-first walk that visits children in sorted character order.

Start here - the target

TO DO

Scenario: Words are listed in lexicographic order

Givena trie with Insert("cat"), Insert("dog"), Insert("car"), Insert("cab") inserted in that order

WhenWords() is called

Thenit returns exactly ["cab", "car", "cat", "dog"]

Andthe order is lexicographic regardless of insertion order, because children are visited sorted

Background

Collecting words is a depth-first walk that builds up the string as it descends: at each node, if end is set the accumulated characters spell a stored word, so record it; then recurse into the children. Because a map has no inherent order, the one thing you must not skip is sorting the child runes before recursing - that is what makes the output deterministic and lexicographic, which every later spec relies on.

Visiting children in ascending character order means a whole subtree comes out sorted: from the root you descend into c before d, and within c you reach cab before car before cat. Insertion order (cat, dog, car, cab) does not matter at all. This exact traversal, started from a prefix node instead of the root, is the next lesson’s completions.

Make it work

func (t *Trie) Words() []string {
  out := []string{}
  var walk func(n *node, prefix string)
  walk = func(n *node, prefix string) {
    if n.end {
      out = append(out, prefix)
    }
    for _, r := range sortedRunes(n.children) { // deterministic order
      walk(n.children[r], prefix+string(r))
    }
  }
  walk(t.root, "")
  return out
}
// sortedRunes returns the child runes of n in ascending order.

CheckpointDONE

You can list every stored word in lexicographic order. Commit and stop here.