Algorithm to convert a table data to hierarchical tree data using Javascript ECMAScript 6

Question

I have a JSON table data and want to convert to JSON tree data as shown below. I'm looking for an efficient algorithm in JavaScript using any new ECMAScript 6 operator or statements with a functional approach (not by standard recursive algorithm with ES5)?

Table data:

[
   {
      "Children":"4th Grand Father"
   },
   {
      "Name":"4th Grand Father",
      "Children":"3rd Grand Father"
   },
   {
      "Name":"3rd Grand Father",
      "Children":"2nd Grand Father"
   },
   {
      "Name":"2nd Grand Father",
      "Children":"Grand Father"
   },
   {
      "Name":"Grand Father",
      "Children":"Father"
   },
   {
      "Name":"Grand Father",
      "Children":"Uncle"
   },
   {
      "Name":"Uncle",
      "Children":"Cousin"
   },
   {
      "Name":"Father",
      "Children":"Brother"
   },
   {
      "Name":"Father",
      "Children":"Me"
   }
]

Tree data:

[
  {
    "Name": "4th Grand Father",
    "Children": [
      {
        "Name": "3rd Grand Father",
        "Children": [
          {
            "Name": "2nd Grand Father",
            "Children": [
              {
                "Name": "Grand Father",
                "Children": [
                  {
                    "Name": "Father",
                    "children": [
                      {
                        "Name": "Brother"
                      },
                      {
                        "Name": "Me"
                      }
                    ]
                  },
                  {
                    "Name": "Uncle",
                    "children": [
                      {
                        "Name": "Cousin"
                      }
                    ]
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
]

Have you tried anything? and why do you care about "new EcmaScript 6" (Which is neither new nor correct term) statements? — Amit
– Amit, Commented Mar 26, 2017 at 19:59
If you don't know the height of the final tree, then you're going to end up using recursion of one form or another. There are plenty of ES6 features which can make your algorithm easier to read in terms of intent, and thus, easier to modify and maintain. But that doesn't take recursion out of the picture. — LetterEh
– LetterEh, Commented Mar 26, 2017 at 21:14
@wonderfulworld Iteration is not going to go the way you think. How many inner loops do you need, if you don't know whether the ancestry ends at "Grandparent" or "Great, Great, Great, Great, Great, Great Grandparent"? To prevent yourself from insanity, you're going to need to traverse children recursively, rather than build 25 nested loops and hope that's enough, and figure out if you're out of children so that you can break early... You should consider adding the recursive solution that you already have, and would like cleaned, so that we can figure out where you're starting from. — LetterEh
– LetterEh, Commented Mar 26, 2017 at 23:03

Community · Accepted Answer · 2020-06-20 09:12:55Z

You could use this ES6 function, which uses a Map, arrow functions, destructured argument assignment. You could even replace the concat call by spread syntax, but I don't think that brings any benefit:

const makeTree = (data) => {
    const hash = data.reduce ( (acc, {Name, Children}) => 
        acc.set(Name, (acc.get(Name) || []).concat(Children)) 
    , new Map );

    const recurse = (Name) => hash.has(Name)
            ?   { Name, Children: hash.get(Name).map(recurse) }
            :   { Name };
    return recurse(undefined).Children;
}

// Sample data
const data = [
   {
      "Children":"4th Grand Father"
   },
   {
      "Name":"4th Grand Father",
      "Children":"3rd Grand Father"
   },
   {
      "Name":"3rd Grand Father",
      "Children":"2nd Grand Father"
   },
   {
      "Name":"2nd Grand Father",
      "Children":"Grand Father"
   },
   {
      "Name":"Grand Father",
      "Children":"Father"
   },
   {
      "Name":"Grand Father",
      "Children":"Uncle"
   },
   {
      "Name":"Uncle",
      "Children":"Cousin"
   },
   {
      "Name":"Father",
      "Children":"Brother"
   },
   {
      "Name":"Father",
      "Children":"Me"
   }
];

const result = makeTree(data);

console.log(result);

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

Explanation:

The hash variable is built from an empty Map, adding the records to it keyed by Name. The value linked to each key is the children information, as an array. When the same Name is encountered (i.e. acc.get(Name) returns something), the child is added to the already existing array, otherwise (|| []) an empty array is created and the child is added to that.

Once the hash is complete, the top of the hierarchy is taken by its missing Name (undefined), and through recursion the children are looked up in the hash and added to the final object.

As the result object is an object with a Children array, and the desired outcome was in fact that array, it is the Children property that gets returned.

Collectives™ on Stack Overflow

Algorithm to convert a table data to hierarchical tree data using Javascript ECMAScript 6

1 Answer 1

Explanation:

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Explanation:

Comments

Your Answer

Sign up or log in

Post as a guest

Related