CODEWITHSUNDEEP
javascripttree
Misha Moroshko
Misha Moroshko

Reputation: 171341

JavaScript trees - elegant solution?

I have multiple trees, for example:

a                  h
| \                | 
b  c               i
 / | \            / \
d  e  f          j   k
   |           / | \
   g          l  m  n

which represented in a single JavaScript object like this:

{ 'a': ['b', 'c'],
  'b': null,
  'c': ['d', 'e', 'f'],
  'd': null,
  'e': ['g'],
  'f': null,
  'g': null,
  'h': ['i'],
  'i': ['j', 'k'],
  'j': ['l', 'm', 'n'],
  'k': null,
  'l': null,
  'm': null,
  'n': null }

i.e. all the nodes appears as keys, and the value of a particular key/node is an array of all its children (or null if it doesn't have children).

I would like to construct two things:

  1. An array of all roots. In this example: ['a', 'h']

  2. For every root, an array of all its descendants, including the root. In this example:

    ['a', 'b', 'c', 'd', 'e', 'f', 'g']

    ['h', 'i', 'j', 'k', 'l', 'm', 'n']

The order of the elements in the resulting arrays doesn't matter.

Could you suggest an elegant method to implement this in JavaScript (jQuery allowed).

Upvotes: 1

Views: 730

Answers (2)

Bergi
Bergi

Reputation: 664513

var tree = {...};
var roots = [], rootdescendants = {};
tl: for (var p in tree) { // tree-loop
    for (var r in rootdescendants)
        // check if p is already in one of the result arrays
        if (rootdescendants[r].lastIndexOf(p)>-1)
            continue tl;
    var d = rootdescendants[p] = [p]; // create new descendants array
    for (var i=0; i<d.length; i++) {
        var c = d[i];
        if (i>0 && c in rootdescendants) { // there is already an array for c
            i += rootdescendants[c].unshift(i, 1) - 3;
            Array.prototype.splice.apply(d, rootdescendants[c]); // insert into d
            delete rootdescendants[c];
        } else {
            if (tree[c]) // not null
                Array.prototype.push.apply(d, tree[c]);
        }
    }
}
roots = Object.keys(rootdescendants);

Upvotes: 0

Andrew D.
Andrew D.

Reputation: 8230

var src = { 'a': ['b', 'c'],
  'b': null,
  'c': ['d', 'e', 'f'],
  'd': null,
  'e': ['g'],
  'f': null,
  'g': null,
  'h': ['i'],
  'i': ['j', 'k'],
  'j': ['l', 'm', 'n'],
  'k': null,
  'l': null,
  'm': null,
  'n': null };

/* ******************************************************************* */

var roots={},p1,p2,isRoot,i=-1;
for(p1 in src){
    isRoot=true;
    for(p2 in src)if(src[p2]&&src[p2].indexOf(p1)>-1){isRoot=false;break;}
    if(isRoot)roots[p1]=[p1];
}
for(p1 in roots){
    i=-1;
    while(++i<roots[p1].length)
        if(src[roots[p1][i]]&&src[roots[p1][i]].length)
            Array.prototype.push.apply(roots[p1],src[roots[p1][i]]);
}

As a result roots variable contains next value for your second task:

    roots: {
        "a": ["a", "b", "c", "d", "e", "f", "g"],
        "h": ["h", "i", "j", "k", "l", "m", "n"]
    }

And for your first task Object.keys(roots) returns needed array.

Upvotes: 1

Related Questions