How to convert a 2D array to a tree (of objects) in JavaScript?

Question

I have a 2D array representing a tree in this format:

[["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]]

Each item (node) is an array where its first element is the name, and the second is the level (depth) of the node.

I need to convert this 2D array to nested JavaScript objects, where each node-object consists of name (string) and children (array of objects). The result should be the root object (here, "Food") with all other items as its children. The input array will always come ordered, so it can be assumed that the first element is root.

What's the best way to go about this, either with iteration or recursion?

How do you know under which object put the nodes? There's no way to know that Milk and Butter go under Dairy with the structure you have. — Alex Turpin
– Alex Turpin, Commented Oct 25, 2011 at 18:53
@Xeon06: Each node goes under the last node encountered with a lower depth, so Milk, Butter and Cheese all go under Dairy; Spinach is the sole child of Vegetables; etc. — George
– George, Commented Oct 25, 2011 at 19:23
Milk, Butter, and Cheese all are of level 2. The last level 1 is Dairy, hence their parent. Fish is also a level 2, but comes after the closer level-1 Meat. So, in general, a higher level node is a parent of all the nodes with lower levels. The next node with the same level number is its sibling. — EmilyT
– EmilyT, Commented Oct 25, 2011 at 19:25

Ben · Accepted Answer · 2011-10-25 19:24:40Z

2

Recursion isn't necessary. I think something like this is what you're looking for:

function tree_from_list(list) {
    var list_node = list.shift();
    var depth = list_node[1];
    var root = {name: list_node[0], children: []};
    var tree_node;
    var cur_nodes = []; 
    cur_nodes[depth] = root;
    while (list.length > 0) {
        list_node = list.shift();
        tree_node = {name: list_node[0], children: []};
        depth = list_node[1];
        if (cur_nodes[depth - 1] === undefined)
            throw 'invalid list!';
        cur_nodes[depth - 1].children.push(tree_node);
        cur_nodes[depth] = tree_node;
    }
    return root;
}
var list = [["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]];
var tree = tree_from_list(list);

edited Oct 25, 2011 at 19:24

answered Oct 25, 2011 at 19:23

Ben

10.1k5 gold badges43 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Wayne · Accepted Answer · 2011-10-25 21:22:18Z

Here's a mostly pointless (and less efficient) recursive solution:

function mktree(lis, lvl) {
    var i, el, c, itemlis = [];
    for (i = 0; el = lis[i++];) {
        if (lvl !== el[1])
            break; 
        var item = {};
        [item[el[0]], c] = mktree(lis.slice(i), lvl + 1);
        i += c - 1; // skip ahead
        itemlis.push(item);
    } 
    return [itemlis, i];
}

function lis_to_tree(arr) {
    return mktree(arr, 0, 0)[0][0];
}

var arr = [["Food", 0], ["Dairy", 1], ["Milk", 2], ["Low-fat", 3], ["2%", 3],
           ["Butter", 2], ["Cheese", 2], ["Vegetables", 1], ["Spinach", 2], 
           ["Meat", 1], ["Fish", 2], ["Salmon", 3], ["Poultry", 2]];
var tree = lis_to_tree(arr);

(Note that this relies on destructuring assignment to skip elements that have already been processed. You could remove this feature, but it would be much slower.)

I call this mostly pointless because it's essentially trying to imitate iteration in the way it maintains a count of elements that it's already processed, so that it can skip ahead in the list. I don't say it's completely useless because I still find the recursive version easier to read than its iterative counterpart.

Collectives™ on Stack Overflow

How to convert a 2D array to a tree (of objects) in JavaScript?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related