Recursive approach for building a tree like object hierarchy does not work as expected

Question

I'm trying to write functionality something like this:

Input:

['A', '-B1', '--B2', '-C1', 'D']

Output:

{'A': {'B1': {'B2': {}}, 'C1': {}}, 'D': {}}

As you can see that B1 and C1 are children of A and B2 is a child of B1. It can go any level nested based on -

I wrote a Javascript code for the same but it seems something wrong when children are created. Here is my code:

function fetch_levels(li, chr='-') {
    var res_list = []
    for (i=0; i<li.length; i++) {
        item = li[i]
        level = item.length - item.replace(RegExp(`^${chr}+`), '').length
        key = item.replace(RegExp(`^${chr}+`), '')
        value = {}
        res_list.push({
            level: level,
            name: key,
            value: value
        })
    }
    return res_list
}

function ttree_to_json(ttree, level=0) {
    result = {}
    for (i = 0; i < ttree.length; i++) {
        cn = ttree[i]
        nn = ttree[i+1] || {'level': -1}

        // Edge cases
        if (cn['level'] > level) {
            continue
        }
        if (cn['level'] < level) {
            return result
        }

        // Recursion
        if (nn['level'] == level) {
            result[cn['name']] = cn['value']
        } else if (nn['level'] > level) {
            rr = ttree_to_json(ttree.slice(i+1), level=nn['level'])
            result[cn['name']] = rr
        }
        else {
            result[cn['name']] = cn['value']
            return result
        }
    }
    return result
}

And this is how the functions can be invoked:

console.log(ttree_to_json(fetch_levels(['A', '-B1', '--B2', '-C', 'D'])))

And the output I got is something like:

Object { B2: {…}, C: {} }

Which is wrong.

Can any help me to figure out what is wrong with the JavaScript code?

The solution is inspired by the sample code mentioned here:

Edit (May 11, 2022)

My bad I didn't give the actual problem. To make the question shorter and precise I gave a different data structure. All the answers are given here work perfectly fine with the above DS. But I cannot make my actual DS to get the desired output.

Here is the actual input:

[
    {
        "componentId": "1067256",
        "componentName": "Readiness",
        "shortHandName": "GTM"
    },
    {
        "componentId": "1067343",
        "componentName": "-Business Planning and Commercialization - BPC",
        "shortHandName": "BPC"
    },
    {
        "componentId": "1068213",
        "componentName": "-SKU Life Cycle Management (SLM)",
        "shortHandName": "SLM"
    },
    {
        "componentId": "1068210",
        "componentName": "--Partner Programs",
        "shortHandName": "Partner"
    },
    {
        "componentId": "1067317",
        "componentName": "--Activation",
        "shortHandName": "Activation"
    },
    {
        "componentId": "1067346",
        "componentName": "Sales Compensation",
        "shortHandName": "Sales Comp"
    }
]

Expected output:

{
    "GTM": {
        "componentId": "1067256",
        "componentName": "Readiness",
        "shortHandName": "GTM",
        "children": {
            "BPC": {
                "componentId": "1067343",
                "componentName": "Business Planning and Commercialization - BPC",
                "shortHandName": "BPC",
                "children": {
                    "Partner": {
                        "componentId": "1068210",
                        "componentName": "Partner Programs",
                        "shortHandName": "Partner",
                        "children": {}
                    },
                    "Activation": {
                        "componentId": "1067317",
                        "componentName": "Activation",
                        "shortHandName": "Activation",
                        "children": {}
                    }
                }
            },
            "SLM": {
                "componentId": "1068213",
                "componentName": "SKU Life Cycle Management (SLM)",
                "shortHandName": "SLM",
                "children": {}
            }
        }
    },
    "Sales Comp": {
        "componentId": "1067346",
        "componentName": "Sales Compensation",
        "shortHandName": "Sales Comp",
        "children": {}
    }
}

Explanation:

• Using the componentName the parent and child relationship (or level) is decided based on - which can go any nested level.
• shortHandName is used as a key and the value which is an object should contain all properties including the newly added attribute children
• children will then be having the same structure and the lowest level child will have {} as children.

To me, it's quite difficult to understand all the answers, so could make them work for the new DS I've mentioned.

Answer 1

You could simplify the code by taking an array for the level references of nested objects.

Any property is assigned to the given level (count of dashes) and it takes object to the next level.

const
    data = ['A', '-B1', '--B2', '-C1', 'D'],
    result = {},
    levels = [result];
    
data.forEach(s => {
    let level = 0;
    while (s[level] === '-') level++;
    s = s.slice(level);
    levels[level][s] = levels[level + 1] = {};
});

console.log(result);

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

Real world problem's solution

const
    data = [{ componentId: "1067256", componentName: "Readiness", shortHandName: "GTM" }, { componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC" }, { componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM" }, { componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner" }, { componentId: "1067317", componentName: "--Activation", shortHandName: "Activation" }, { componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp" }],
    getLevelString = (string, level = 0) => string[0] === '-'
        ? getLevelString(string.slice(1), level + 1)
        : { level, string },
    result = data
        .reduce((levels, o) => {
            const { level, string: componentName } = getLevelString(o.componentName);
            levels[level][o.shortHandName] = { ...o, componentName, children: levels[level + 1] = {} };
            return levels;
        }, [{}])
        [0];

console.log(result);

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

Answer 2

There is no recursion needed. Since the only reliable information about the to be added (next) nesting level is carried by the dashes count, one can add the next level anyway just to the object reference of the most recently processed previous/lower level.

Thus a lookup in form of an array which refers by its index to each recently created level/branch is everything needed for a simple loop based solution.

The next provided implementation uses a reduce based approach.

function aggregateObjectHierarchyLevel(
  { recentLevels, result = {} },
  item,
  idx,
) {
  // handle/synchronize the initial `result` reference.
  if (idx === 0) {
    recentLevels = [result];
  }
  const [_, dashes = '', key = ''] = item.match(/^([-]*)(.*)/) ?? [];
  const level = dashes.length;

  recentLevels[level + 1] = recentLevels[level][key] = {};

  return { recentLevels, result };
};


console.log(
  ['A', '-B1', '--B2', '-C1', 'D']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)
console.log(
  ['A', '-B1', '--B2', '---B3', '-C1', 'D']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)
console.log(
  ['A', '-B1', '--B2', '---B3', '--C2', '---C3', '-D1', 'E']
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
)

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

Edit ... due to the OP's real world data changes

From my above comment ...

"@SauravKumar ... from what the OP was presenting before (and the base problem / hierarchy does not change) the expected output of what the OP refers to as "the actual input" does not match the basic building pattern. '--Partner Programs' and '--Activation' have to be the children of '-SKU Life Cycle Management (SLM)' and not of '-Business Planning and Commercialization - BPC'. If the OP wants the expected output, the input array needs to be changed to the two former mentioned child items become direct followers of the latter (parent) item."

The update/refactoring from the above code to the next provided one took just 3 minutes which proves the robustness of the first approach.

The only changes within the reducer function were due to the necessary object destructuring and object re/assembling. The main approach at no point needed to be changed.

function aggregateObjectHierarchyLevel(
  { recentLevels, result = {} },
  { shortHandName, componentName: name , ...itemEntriesRest },
  idx,
) {
  // handle/synchronize the initial `result` reference.
  if (idx === 0) {
    recentLevels = [result];
  }
  const [_, dashes = '', componentName = ''] = name.match(/^([-]*)(.*)/) ?? [];
  const level = dashes.length;

  recentLevels[level][shortHandName] = {
    shortHandName,
    componentName,
    ...itemEntriesRest,
    children: recentLevels[level + 1] = {},
  };
  return { recentLevels, result };
};

const data = [
  { componentId: "1067256", componentName: "Readiness", shortHandName: "GTM" },
  { componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC" },
  { componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM" },
  { componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner" },
  { componentId: "1067317", componentName: "--Activation", shortHandName: "Activation" },
  { componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp" }
];

console.log(
  data
    .reduce(aggregateObjectHierarchyLevel, {})
    .result
);

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

Answer 3

Another version, quite similar in design to both Peter's and Nina's, but with a different coding style, looks like this:

const nest = (strings, result = {}) => strings .reduce (
  (levels, str, _, __, [___, hyphens, val] = str .match (/(\-*)(.+)/), lvl = hyphens .length) => (
    (levels [lvl] [val] = levels [lvl + 1] = {}), 
    levels
  ), [result]
) [0]

console .log (nest (['A', '-B1', '--B2', '-C1', 'D']))

We use the same nesting structure as both those answers, and use a similar regex as Peter to separate out the two parts of the string, and the same updating logic as in both of those answers. Here we do this in a .reduce call, with only the hidden accumulator being modified.

I wrote this independently of those, came back and saw that there were already two good answers, but thought this was enough different to include as well. (I also fixed it to steal Peter's destructuring of the regex match call. Much better than my original .slice (1, 3)-then-destructure approach!)

It's interesting to see three very different coding styles all approach the problem with the same fundamental design!

Update

This version handles the updated requirements in the question. In the future, with that much change, please simply start a second question and include a link back to the original for context. (You might still want to do this, as new questions get more attention.)

const nest = (input, result = {children: {}}) => input .reduce ((
  levels, 
  {componentId, componentName, shortHandName}, 
   _, __, [___, hyphens, val] = componentName .match (/(\-*)(.+)/), lvl = hyphens .length
) => (
  (levels [lvl] .children [shortHandName] = levels [lvl + 1] = {
    componentId, componentName: val, shortHandName, children: {}
  }), 
  levels
), [result]) [0] .children

const input = [{componentId: "1067256", componentName: "Readiness", shortHandName: "GTM"}, {componentId: "1067343", componentName: "-Business Planning and Commercialization - BPC", shortHandName: "BPC"}, {componentId: "1068213", componentName: "-SKU Life Cycle Management (SLM)", shortHandName: "SLM"}, {componentId: "1068210", componentName: "--Partner Programs", shortHandName: "Partner"}, {componentId: "1067317", componentName: "--Activation", shortHandName: "Activation"}, {componentId: "1067346", componentName: "Sales Compensation", shortHandName: "Sales Comp"}]

console .log (nest (input))

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

Note that this does not match your target output, nesting Partner and Activation inside SLM, not in BPC. But that seems to be correct given the input data. If you wanted to switch that, then SLM would have to come later in the input array.

There's not much more to say about the design. It's the exact same design as above, except with more fields, including a nested children one.