How to loop through Object and create a tree Object

Question

I have a flat object and an array from which I need to construct a tree-like object.

choices: ['choice1', 'choice2', 'choice3'];
items: [
    {
        choice1: 'taste',
        choice2: 'good',
        choice3: 'green-lemon'
    },
    {
        choice1: 'taste',
        choice2: 'bad',
        choice3: 'green-lemon'
    }
];

The array describes the level at which each choice will come in the tree. I do not know how many choices, items or levels there will be later.

How do I get the following object:

output: {
    taste: {
        good: {
            green-lemon:1
        },
        bad: {
            green-lemon:1
        }
    }
}

I need to get an object describing how many items there are on each level. In this example this is choice1: 1; choice2: 2 and each choice3: 1.

Any advice on how to build a loop to get this result?

Are there going to be more levels than this? Will this data set ever expand? — Dr Rob Lang
– Dr Rob Lang, Commented Nov 27, 2013 at 8:51
Is the choices array meant to describe the level at which each choice comes in the tree? @brainwipe's question is also relevant to a correct solution. — Jordan Gray
– Jordan Gray, Commented Nov 27, 2013 at 8:56
@brainwipe: There might be only 2 levels of choices and there might be 5 levels of choices. The choices array and the items object will never change during runtime. — Dinkheller
– Dinkheller, Commented Nov 27, 2013 at 8:58
@JordanGray: items contains more data. The choices array describes the tree as level0 would be the first item and the last level the last item. — Dinkheller
– Dinkheller, Commented Nov 27, 2013 at 9:01
@ProtoBassi That's helpful. Do you want to come out with the tree, the item count or both as the result of the array? — Jordan Gray
– Jordan Gray, Commented Nov 27, 2013 at 9:02

Dr Rob Lang · Accepted Answer · 2013-11-27 10:12:40Z

I think the best solution here is a loop with some recursion. I have increased the size of the model in the example to show it going with n levels. Check the output with your javascript console.

var choices = ['choice1', 'choice2', 'choice3'];
var items = [{
    choice1: 'taste',
    choice2: 'good',
    choice3: 'green-lemon'
}, {
    choice1: 'taste',
    choice2: 'bad',
    choice3: 'green-lemon'
},
{
    choice1: 'taste',
    choice2: 'ok',
    choice3: 'green-lemon'
},
{
    choice1: 'taste',
    choice2: 'ok',
    choice3: 'green-lemon'
}];

function IsLastLevel(levelIndex) {
    return (levelIndex == choices.length - 1);
}

function HandleLevel(currentItem, currentLevel, nextChoiceIndex) {

    var nextLevelName = currentItem[choices[nextChoiceIndex]];

    if (typeof currentLevel[nextLevelName] === 'undefined') {
        currentLevel[nextLevelName] = {};
    }

    if (IsLastLevel(nextChoiceIndex)) {
        if (currentLevel[nextLevelName] > 0) {
            currentLevel[nextLevelName]++;
        } else {
            currentLevel[nextLevelName] = 1;
        }
    } else {
        var goOneDeeper = nextChoiceIndex + 1;
        HandleLevel(currentItem, currentLevel[nextLevelName], goOneDeeper);
    }
}

var output = {};

for(var itemIndex in items)
{
    var item = items[itemIndex];
    HandleLevel(item, output, 0);
}

console.log(output);

JsFiddle Demo

animuson · Accepted Answer · 2014-01-27 01:22:00Z

2

Brainwipe has already given a very clean answer, but I thought I would try my hand anyway. This solution works by recursively reducing the list of items, level by level, until it reaches the leaf nodes.

function choiceTree(items, choices) {
    // Return empty object if there were no choices.
    if (!choices.length) return {};

    var choice = choices.shift();

    // Construct the current level of the tree.
    var level = items.reduce(function(node, item) {
        var value = item[choice];

        // Add item if branch node or set to 1 if leaf node.
        node[value] = (choices.length)
            ? (node[value] || []).concat(item)
            : 1;

        return node;
    }, {});

    // Return if there are no remaining choices.
    if (!choices.length) return level;

    // Recursively construct the next level.
    for (var node in level)
        level[node] = choiceTree(level[node], choices.slice());

    return level;
}

jsFiddle demo

edited Jan 27, 2014 at 1:22

animuson♦

54.9k28 gold badges142 silver badges150 bronze badges

answered Nov 27, 2013 at 11:40

Jordan Gray

16.5k3 gold badges56 silver badges70 bronze badges

2 Comments

Dinkheller Over a year ago

Thanks a lot, too. It is way less code, but harder to read. I have not worked with reduce yet, but will definately take a look at it. Thanks.

Jordan Gray Over a year ago

Array.reduce is really cool and underused, you should definitely read up on it! :) All it does is "reduce" an array to a single value; you could use a for loop instead, but I think the extra code is messier. It's not supported in IE 8 and below, but it's easy to shim.

Collectives™ on Stack Overflow

How to loop through Object and create a tree Object

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related