Create a Tree/Trie from a word

Question

I need some help to create a javascript algorithm that builds a tree out of a word. The nodes of the tree are the letters of the word that are always in alphabetical order. Ex. 'balance' should be this object:

  const tree = {
    b: {
      l: {
        n: {}
      },
      n: {}
    },
    a: {
      l: {
        n: {

        }
      },
      n: {

      },
      c: {
        e: {

        }
      },
      e: {

      }
    }
....
  }
}

  const asArray = a.split('')
  const tree = {}
  for (let i = 0; i < a.length; i++) {
    const letter = array[i];
    const greaterThan = asArray.filter((value, index) => {
      return value > letter && index > i
    })
    tree[letter] = {}
    for (let j = 0; j < greaterThan.length; j++) {
      const gt = greaterThan[j];
      tree[letter][gt] = {}
    }
  }

A javascript object, which the keys are the letters.

Answer 1

You could get all parts of the string who are in order and then build the tree.

function getParts(string) {
    function iter(i, left) {
        var last = left[left.length - 1];
        if (i >= string.length) {
            if (left.length) result.push(left);
            return;
        }
        if (!last || last < string[i] ) iter(i + 1, left.concat(string[i]));
        iter(i + 1, left);
    }

    var result = [];
    iter(0, []);
    return result;
}

var string = 'balance',
    tree = getParts(string).reduce((r, a) => {
        a.reduce((o, k) => o[k] = o[k] || {}, r);
        return r
    }, {});

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }

A complete recursive style.

function setParts(target, [key, ...values], last = '') {
    if (!key) return;
    if (last < key) setParts(target[key] = target[key] || {}, values, key);
    setParts(target, values, last);
}

var string = 'balance',
    tree = {};

setParts(tree, string);

console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }