Most efficient way to split string into tree structure

Anita Ghising 0
Viewed 68

I have a dynamic array of the string. Each string represents the node of the tree. If any string has "_", I want to split into each node and store it in another array.

For. e.g. '0_2_0_0' needs to split into "0", "0_2", "0_2_0", & "0_2_0_0" then store it in the new array. I've achieved it by using the multiple for loops. I do not think this is the most efficient way of doing it.

let visibleTreeNodes = [];
const treeData = ['0_0', '0_1', '0_2_0_0', '1'];

for (let i = 0; i < treeData.length; i++) {
    if (treeData[i].includes('_')) {
        const nodesArray = treeData[i].split('_');
        for (let i = 0; i < nodesArray.length; i++) {
            let node = nodesArray[0];
            for (let j = 0; j <= i; j++) {
                if (j !== 0) {
                    node = node + '_' + nodesArray[j];
                }
            }
            if (visibleTreeNodes.indexOf(node) === -1) {
                visibleTreeNodes.push(node)
            }
        }

    } else if (visibleTreeNodes.indexOf(treeData[i]) === -1) {
        visibleTreeNodes.push(treeData[i])
    }
}
console.log(treeData);
console.log(visibleTreeNodes);

javascript
4 Answers

You could build a tree first and then get the pathes from the keys.

const
    getFlat = object => Object.keys(object).flatMap(k => [
        k,
        ...getFlat(object[k]).map(p => `${k}_${p}`)
    ]),
    data = ['0_0', '0_1', '0_2_0_0', '1'],
    result = getFlat(data.reduce((t, s) => {
        s.split('_').reduce((o, k) => o[k] ??= {}, t);
        return t;
    }, {}));

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

Nina Scholz0

A "one-liner": 

const treeData = ['0_0', '0_1', '0_2_0_0', '1'];
const visibleTreeNodes = [...new Set(treeData.flatMap(
   s=>s.split('_').reduce((a, si, i)=> [...a, a[i-1]+'_'+si])
))];// Set used to remove duplicates
console.log(visibleTreeNodes)
though efficiency must be tested - a more concise solution doesn't automatically result in a shorter run time

kikon0

I tried to simplify your equation. I reached this below snippet. It has a forEach and then a while loop inside forEach for every input string.

let visibleTreeNodes = [];
const treeData = ['0_0', '0_1', '0_2_0_0', '1'];

treeData.forEach(x => {
  const arr = x.split("_");
  let i = 0;
  let node = arr[0];

  while (i < arr.length) {
    if (!visibleTreeNodes.includes(node)) {
      visibleTreeNodes.push(node);
    }
    node = [node, arr[i + 1]].join("_");
    i++;
  }
});

console.log(treeData);
console.log(visibleTreeNodes);

You are free to figure out any better solution.

Thanks

Rohit Khandelwal0

All that is left for me is to explain (and remember) the part of building the tree by @Nina Scholz. I'll basically rename the variables and use familiar syntax.

// data can be directories lists
const data = ['0_0', '0_1', '0_2_0_0', '1']

// the classic group by using reduce
var result = data.reduce(function(agg, item) {

  // buliding tree path incrementally
  var pointer = agg;
  item.split('_').forEach(function(part) {
    pointer[part] = pointer[part] || {}
    pointer = pointer[part];
  });

  return agg;
}, {});

// result is classic object tree 
console.log(result);

// iterate to print desired output:
function iterate(tree, parent) {
  Object.keys(tree).forEach(function(key) {
    var value = tree[key];
    var full = (parent ? parent + "_"  : '') + key
    console.log(full)
    if (typeof value === 'object') {
      iterate(value, full)
    }
  })
}

iterate(result)
.as-console-wrapper {max-height: 100% !important}

IT goldman0
Related