Basic auto-completion functionality with trie data structure

tries.js

// Code originnaly belong to Front End Masters course
// 4 Semesters of CS in 5 Hours part II
//https://btholt.github.io/four-semesters-of-cs-part-two/
 
const CITY_NAMES = [
  "New York",
  "Los Angeles",
  "Chicago",
  "Houston",
  "Philadelphia",
  "Phoenix",
  "San Antonio",
  "San Diego",
  "Dallas",
  "San Jose",
  "Austin",
  "Indianapolis",
  "Jacksonville",
  "San Francisco",
  "Columbus",
  "Charlotte",
  "Fort Worth",
  "Detroit",
  "El Paso",
  "Memphis",
  "Seattle",
  "Denver",
  "Washington",
  "Boston",
  "Nashville Davidson",
  "Baltimore",
  "Oklahoma City",
  "Louisville",
  "Portland",
  "Las Vegas",
  "Milwaukee",
  "Albuquerque",
  "Tucson",
  "Fresno",
  "Sacramento",
  "Long Beach",
  "Kansas City",
  "Mesa",
  "Virginia Beach",
  "Atlanta",
  "Colorado Springs",
  "Omaha",
  "Raleigh",
  "Miami",
  "Oakland",
  "Minneapolis",
  "Tulsa",
  "Cleveland",
  "Wichita",
]

class Node {
  children = []
  value = ""
  terminus = false

  constructor(string) {
    this.value = string[0] || ""
    if (string.length > 1) {
      this.children.push(new Node(string.substring(1)))
    } else {
      this.terminus = true
    }
  }
  add(string) {
    const value = string[0]
    const next = string.substring(1)
    for (let i = 0; i < this.children.length; i++) {
      const child = this.children[i]
      if (child.value === value) {
        if (next) {
          child.add(next)
        } else {
          child.terminus = true
        }
        return
      }
    }
    this.children.push(new Node(string))
  }
  _complete(search, built, suggestions) {
    if (suggestions.length >= 3 || (search && search[0] != this.value)) {
      return suggestions
    }

    if (this.terminus) {
      suggestions.push(`${built}${this.value}`)
    }

    this.children.forEach((child) => {
      child._complete(search.substring(1), `${built}${this.value}`, suggestions)
    })

    return suggestions
  }
  complete(string) {
    return this.children
      .map((child) => child._complete(string, "", []))
      .reduce((acc, item) => acc.concat(item))
  }
}

const createTrie = (words) => {
  const root = new Node("")

  words.forEach((word) => {
    root.add(word.toLowerCase())
  })

  return root
}

let root = createTrie(CITY_NAMES.slice(0, 10))
let completions = root.complete("san")
console.log(completions) // ["san antonio", "san diego", "san jose"]

root = createTrie(CITY_NAMES.slice(0, 10));
completions = root.complete("philadelph");
console.log(completions) // ["philadelphia"]