title: How to paginate a trie, so you can find 100 words matching prefix in the trie, starting at a paginated offset?
body: <p>I am using a <a href="https://gist.github.com/tpae/72e1c54471e88b689f85ad2b3940a8f0" rel="nofollow noreferrer">trie</a> made to work on alphabets/scripts from any language.</p>
  <pre><code>class TrieNode {
    constructor(key) {
      // the &quot;key&quot; value will be the character in sequence
      this.key = key;
  
      // we keep a reference to parent
      this.parent = null;
  
      // we have hash of children
      this.children = {};
  
      // check to see if the node is at the end
      this.end = false;
    }
  
    getWord() {
      let output = [];
      let node = this;
  
      while (node !== null) {
        output.unshift(node.key)
        node = node.parent
      }
  
      return output.join('')
    }
  }
  
  class Trie {
    constructor() {
      this.base = new TrieNode(null)
    }
  
    insert(word) {
      let node = this.base
  
      const points = Array.from(word)
  
      for (const i in points) {
        const point = points[i]
        if (!node.children[point]) {
          const child = node.children[point] = new TrieNode(point)
          child.parent = node
        }
  
        node = node.children[point]
  
        if (i == word.length - 1) {
          node.end = true
        }
      }
    }
  
    contains(word) {
      let node = this.base
  
      const points = Array.from(word)
  
      for (const i in points) {
        const point = points[i]
  
        if (node.children[point]) {
          node = node.children[point]
        } else {
          return false
        }
      }
  
      return node.end;
    }
  
    find(prefix) {
      let node = this.base
      let output = []
  
      const points = Array.from(prefix)
  
      for (const i in points) {
        const point = points[i]
  
        // make sure prefix actually has words
        if (node.children[point]) {
          node = node.children[point]
        } else {
          // there's none. just return it.
          return output
        }
      }
  
      const stack = [node]
      while (stack.length) {
        node = stack.shift()
        // base case, if node is at a word, push to output
        if (node.end) {
          output.unshift(node.getWord())
        }
  
        // iterate through each children, call recursive findAllWords
        for (var child in node.children) {
          stack.push(node.children[child])
        }
      }
  
      return output
    }
  }
  </code></pre>
  <p>Here is how you can find all words matching prefix. <a href="https://raw.githubusercontent.com/zeisler/scrabble/578378ae0f056273b281081fb62f9c7c3aa84f60/db/dictionary.csv" rel="nofollow noreferrer">These scrabble words</a> were used (<code>tmp/scrabble.csv</code>).</p>
  <pre><code>const fs = require('fs')
  const Trie = require('./Trie')
  
  const words = fs.readFileSync('tmp/scrabble.csv', 'utf-8')
    .trim()
    .split(/\n+/)
    .map(x =&gt; x.trim())
  
  const trie = new Trie()
  
  words.forEach(word =&gt; trie.insert(word))
  
  console.log(trie.find('zy'))
  [
    'zygodactylous', 'zygomorphies', 'zygapophysis',
    'zygapophyses',  'zygomorphic',  'zymologies',
    'zygospores',    'zygosities',   'zygomorphy',
    'zygodactyl',    'zymurgies',    'zymograms',
    'zymogenes',     'zygotenes',    'zygospore',
    'zygomatic',     'zyzzyvas',     'zymosans',
    'zymology',      'zymogram',     'zymogens',
    'zymogene',      'zygotene',     'zygosity',
    'zygomata',      'zyzzyva',      'zymurgy',
    'zymotic',       'zymosis',      'zymoses',
    'zymosan',       'zymogen',      'zymases',
    'zygotic',       'zygotes',      'zygosis',
    'zygoses',       'zygomas',      'zydecos',
    'zymase',        'zygote',       'zygose',
    'zygoma',        'zygoid',       'zydeco',
    'zymes',         'zyme'
  ]
  </code></pre>
  <p>However, search <code>find('a')</code> will find over 10,000 matches (words starting with <code>a</code>). If this were a web app, you might not want to show all 10,000 at once, maybe only 100 or 1,000 at a time. How could you implement a pagination system against this trie? Is it possible?</p>
  <p>From my initial thought-attempts, I was trying to think how you could keep track of the &quot;path&quot; you left off with in the trie (say we are paginating 100 matches/words at a time). So I am trying to modify this function:</p>
  <pre><code>class Trie {
    // ...
  
    find(prefix, max = 100) {
      let node = this.base
      let output = []
  
      const points = Array.from(prefix)
  
      for (const i in points) {
        const point = points[i]
  
        // make sure prefix actually has words
        if (node.children[point]) {
          node = node.children[point]
        } else {
          // return path [-1] since there is no match?
          return [output, [-1]]
        }
      }
  
      const stack = [node]
      const pathStack = [[0]]
      while (stack.length) {
        const path = pathStack.shift()
        node = stack.shift()
        // base case, if node is at a word, push to output
        if (node.end) {
          output.unshift(node.getWord())
          if (output.length === max) {
            return [output, path]
          }
        }
  
        // iterate through each children, call recursive findAllWords
        let i = 0
        for (var child in node.children) {
          pathStack.push(path.concat(i++))
          stack.push(node.children[child])
        }
      }
  
      return [output, [-1]]
    }
  }
  </code></pre>
  <p>Maybe this is partially correct? But I don't see how to use the path to jump back to the right spot on the next query.</p>
  <pre><code>[
    [
      'abye', 'abut', 'abri', 'abos', 'ably', 'able', 'abet', 'abed',
      'abbe', 'abba', 'abas', 'aals', 'aahs', 'azo',  'ays',  'aye',
      'axe',  'awn',  'awl',  'awe',  'awa',  'avo',  'ave',  'ava',
      'auk',  'att',  'ate',  'ass',  'asp',  'ask',  'ash',  'art',
      'ars',  'arm',  'ark',  'arf',  'are',  'arc',  'arb',  'apt',
      'ape',  'any',  'ant',  'ani',  'ane',  'and',  'ana',  'amu',
      'amp',  'ami',  'ama',  'alt',  'als',  'alp',  'all',  'ale',
      'alb',  'ala',  'ait',  'ais',  'air',  'ain',  'aim',  'ail',
      'aid',  'aha',  'ago',  'age',  'aga',  'aft',  'aff',  'adz',
      'ads',  'ado',  'add',  'act',  'ace',  'aby',  'abs',  'abo',
      'aba',  'aas',  'aal',  'aah',  'ay',   'ax',   'aw',   'at',
      'as',   'ar',   'an',   'am',   'al',   'ai',   'ah',   'ag',
      'ae',   'ad',   'ab',   'aa'
    ],
    [ 0, 1, 17, 0 ]
  ]
  </code></pre>
  <p>And plus, the words appear to be in unusual order, maybe I am not inserting them the correct order?</p>
  <p>This way, in theory, if you had the <code>path</code>, then when you call <code>find(prefix, startAtPath)</code>, you would pass the <code>startAtPath</code> as a second parameter, and start the search from that point forward, to get the next 100 words. I haven't seen any &quot;trie pagination&quot; examples on the web, so maybe it's not a thing that's possible, not sure.</p>