Random numbers not in a big list using search trees in JS

random-number-search-trees.js

// This is some numbers from our database. Let's have them as strings
// as we will work with the individual digits.
// For SIMPLICITY, all numbers will be 4 digits. You could zero-pad them
// if you needed to.
const numbers = ['1234', '5678', '9012', '3456', '7890', '1239', '9024'];

// We will build a "tree" of the digits represented by a multi-dimensional
// "array". For just the first number we would expect:
// {
//   '1': {
//     '2': {
//       '3': {
//         '4': true
//       }
//     }
//   }
// }

/**
 * Build the tree
 *
 * @param {string[]} numberList
 * @return {object}
 */
function buildSearchTree(numberList) {
  const tree = {};
  numberList.forEach((x) => addToTree(tree, x));
  return tree;
}

/**
 * Adds string representation of number to the tree object
 *
 * @param {object} tree  The tree object
 * @param {string} x     The stringified number to add
 */
function addToTree(tree, x) {
  // Split the string into characters and send to the recursive
  // worker.
  const digits = x.split('');
  return addToTreeRecursively(tree, digits);
}

/**
 *
 * @param {object} tree      The tree object
 * @param {string[]} digits  Array of digit characters
 */
function addToTreeRecursively(tree, digits) {
  if (digits.length === 0) {
    return true;
  }

  if (!treeHasDigit(tree, digits[0])) {
    tree[digits[0]] = {};
  }

  const remainingDigits = digits.slice(1);

  const newSubTree = addToTreeRecursively(tree[digits[0]], remainingDigits);
  tree[digits[0]] = newSubTree;

  return tree;
}

function treeHasDigit(tree, digit) {
  return Object.keys(tree).includes(digit);
}

/**
 * @param {object} tree
 * @param {string} x
 */
function isNumberInTree(tree, x) {
  // Split the stringified number and pass to the recursive worker
  const digits = x.split('');
  return isNumberInTreeRecursive(tree, digits);
}

function isNumberInTreeRecursive(tree, digits) {
  if (tree === true) {
    return true;
  }

  if (Object.keys(tree).includes(digits[0])) {
    const remainingDigits = digits.slice(1);
    return isNumberInTreeRecursive(tree[digits[0]], remainingDigits);
  }

  return false;
}

function getRandomDigit() {
  return Math.floor(Math.random() * 10).toString(10);
}

function generateRandomNotInTree(tree, numDigits = 4) {
  if (numDigits === 0) {
    return '';
  }

  let thisDigit = getRandomDigit();
  while (isNumberInTree(tree, thisDigit)) {
    thisDigit = getRandomDigit();
  }
  // Not sure what to do. Backtrack if no options?
  const moreDigits = generateRandomNotInTree(tree, (numDigits = 1));
}

const t = buildSearchTree(numbers);

// isNumberInTree(t, '1234');