T9 blogpost - 7

gistfile1.js

function getDeeperSuggestions(root, maxDepth) {
  // We traverse down every possible branch from the result node (the node 
  // corresponding to the keypad entry), saving words we see as we go and 
  // stopping when we reach the specified depth.sug
  
  // deepSuggestions is an array with (maxDepth) subarrays.
  // Each of the subarrays will be one depth level's suggestions.
  var deepSuggestions = [];
  while(deepSuggestions.length < maxDepth) {
    deepSuggestions.push([]);
  }

  // The traverse function (below) fills deepSuggestions with results.
  traverse(root, 0);

  // Each level is sorted individually, because we want shallower results
  // to always be suggested first. (this is an implementation detail and 
  // there's a possibility sorting everything together might give 
  // better results in practice.)
  deepSuggestions = deepSuggestions.map(function(level) {
    return level.sort(function(a, b) {
      return b[1] - a[1];
    });
  });

  // At this point, deepSuggestions is an array of arrays (one for each 
  // level of depth). Each of those subarrays contains word tuples.
  return deepSuggestions.reduce(function(result, level) {
    // Merge each level into a single flat array.
    return result.concat(level.map(function(wordTuple) {
      // Keep only the word itself, discarding the frequency number
      return wordTuple[0];
    }));
  }, []);
    
  function traverse(root, depth) {
    // Basic tree traversal, collecting results up to the required depth.
    if(depth <= maxDepth && depth !== 0) { // Result already has depth 0
      var d = depth - 1;
      deepSuggestions[d] = deepSuggestions[d].concat(root.words);
    }
    
    if(depth === maxDepth) { return; }

    for(var childKey in root.children) {
      traverse(root.children[childKey], depth + 1);
    }
  }    
}