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.

that is unusual. with a single word, you get only one branch. — Nina Scholz, Apr 16 '19 at 12:59
yeah, I'd expect `balance` to yield `{b:{a:{l:{a:{n{c:{e:{}}}}}}}}` or something like that. What is the rule for generating this structure? — VLAZ, Apr 16 '19 at 13:06
`The nodes of the tree are the letters of the word that are always in alphabetical order` and how would this work when [object keys don't have a guaranteed iteration order](https://stackoverflow.com/questions/5525795/does-javascript-guarantee-object-property-order)? — VLAZ, Apr 16 '19 at 13:08
@NinaScholz actually each letter yields its own tree. There is no single root node in this case. The firs level of the object are kinda of roots of their trees. — Thiago Caramelo, Apr 16 '19 at 13:22
@VLAZ The rule is to loop through all letters of the word and from there you start to branch their own tree. Well if the objects are nested I'd say the order doesn't matter right ? — Thiago Caramelo, Apr 16 '19 at 13:24

Nina Scholz · Accepted Answer · 2019-04-16T17:12:13.493

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; }

Great ! But why a letter does not yield a : c : e ? – Thiago Caramelo Apr 16 '19 at 13:45 — Thiago Caramelo, Apr 16 '19 at 13:45

Create a Tree/Trie from a word

1 Answers1