function Node() {
      this.endCount = 0
      this.word = ''
      this.children = {}
    }
    class Tire {
      constructor() {
        this.root = new Node()
      }
      addWord(word) {
        var node = this.root;
        for (let next of word) {
          if (!node.children[next]) {
            node.children[next] = new Node()
          }
          node = node.children[next]
        }
        node.word = word;
        node.endCount++
      }
      search(k) {
        var ret = []
        innerSearch(this.root, k, ret)
        return ret
      }
    }
    function innerSearch(node, k, ret) {
      if (node) {
        if (node.endCount === k) {
          ret.push(node.word)
        }
        for (let next in node.children) {
          innerSearch(node.children[next], k, ret)
        }
      }
    }

    var topKFrequent = function (words, k) {
      var tire = new Tire;
      for (let word of words) {
        tire.addWord(word)
      }
      return tire.search(k)
    };