Nested Tree structure object trying to extract and get information Json object

Question

I would like to know the correct way to create a nested Json tree Structure object in javascript. data structure containing objects and arrays. How can I extract the information, i.e. access a specific or multiple values (or id)?

I have a very deep nested tree structure Json and I am given an object that can exist at any depth. I need to be able to iterate through all grandparent / parent / children nodes until I find the requested category, plus be able to capture its grandparent / parent / children categories all the way through.

//input data structure

[{
    "Type": "grdparent1",
    "name": "grdparent1",
    "children": [{
        "Type": "grdparent1",
        "Id": 45,
        "children": []
    }, {
        "Type": "grdparent1",
        "Id": 46,
        "children": [{
            "Type": "parent1",
            "Id": 54,
            "children": [{
                "Type": "child1",
                "Id": 63,
                "children": []
            }, {
                "Type": "child2",
                "Id": 64,
                "children": []
            }]
        }, {
            "Type": "parent2",
            "Id": 57,
            "children": []
        }]
    }]
}, {
    "Type": "grdparent2",
    "name": "grdparent2",
    "children": [{
        "Type": "grdparent2",
        "Id": 4,
        "children": [{
            "Type": "parent1",
            "Id": 16,
            "children": [{
                "children": [],
                "Type": "child1",
                "Id": 28,
            }]
        }, {
            "Type": "parent2",
            "Id": 17,
            "children": []
        }]
    }]
}, {
    "Type": "grdparent3",
    "name": "grdparent3",
    "children": []
}, {
    "Type": "grdparent4",
    "name": "grdparent4",
    "children": [{
        "Type": "parent1",
        "Id": 167,
        "children": []
    }]
}]

//output

[{
    "grdparent1": [{
        "Id": 45,
    }, {
        "Id": 46,
        "parent1": [{
            "Id": 54,
            "child1": {
                "Id": 63
            }
        }, {
            "child2": {
                "Id": 64
            }
        }]
    }, {
        "parent2": [{
            "Id": 57
        }]
    }]
}, {
    "grdparent2": [{
        "Id": 4,
        "parent1": [{
            "Id": 16,
            "child1": [{
                "Id": 28
            }]
        }, {
            "parent2": [{
                "Id": 17
            }]
        }]
    }, {
        "grdparent4": [{
            "parent1": [{
                "Id": 167
            }]
        }]
    }]
}]

Answer 1

Here is the code. You have the result in output variable:

    var input = [{
        "Type": "grdparent1",
        "name": "grdparent1",
        "children": [{
            "Type": "grdparent1",
            "Id": 45,
            "children": []
        }, {
            "Type": "grdparent1",   
            "Id": 46,
            "children": [{
                "Type": "parent1",
                "Id": 54,
                "children": [{
                    "Type": "child1",
                    "Id": 63,
                    "children": []
                }, {
                    "Type": "child2",
                    "Id": 64,
                    "children": []
                }]
            }, {
                "Type": "parent2",
                "Id": 57,
                "children": []
            }]
        }]
    }, {
        "Type": "grdparent2",
        "name": "grdparent2",
        "children": [{
            "Type": "grdparent2",
            "Id": 4,
            "children": [{
                "Type": "parent1",
                "Id": 16,
                "children": [{
                    "children": [],
                    "Type": "child1",
                    "Id": 28,
                }]
            }, {
                "Type": "parent2",
                "Id": 17,
                "children": []
            }]
        }]
    }, {
        "Type": "grdparent3",
        "name": "grdparent3",
        "children": []
    }, {
        "Type": "grdparent4",
        "name": "grdparent4",
        "children": [{
            "Type": "parent1",
            "Id": 167,
            "children": []
        }]
    }];

    var output = [];

    for(var index = 0; index < input.length; index++) {
        if(input[index].children.length > 0) {
            var parsedObject = parseTopLevelItem(input[index]);
            if(parsedObject) {
                output[output.length] = parsedObject;
            }
        }
    }

alert(JSON.stringify(output));

    function parseTopLevelItem(item) {
        var topLevelReturnObject;
        if(item.children.length > 0) {
            topLevelReturnObject = {};
            for(var i = 0; i < item.children.length; i++) {
                var parsedObject = parseChild(item.children[i]);
                if(parsedObject) {
                    var key = parsedObject[0];
                    if(!topLevelReturnObject[key]) {
                        topLevelReturnObject[key] = [];
                    }
                    topLevelReturnObject[key][(topLevelReturnObject[key]).length] = parsedObject[1];
                }
            }
        }
        return topLevelReturnObject;
    }

    function parseChild(childElement){
        var returnObject = [];
        returnObject[0] = childElement.Type;
        returnObject[1] = {};
        returnObject[1].Id = childElement.Id;

        for(var i = 0; i < childElement.children.length; i++) {
                var parsedObject = parseChild(childElement.children[i]);
                if(parsedObject) {
                    var key = parsedObject[0];
                    if(!returnObject[1][key]) {
                        returnObject[1][key] = [];
                    }
                    returnObject[1][key][(returnObject[1][key]).length] = parsedObject[1];
                }
        }

        return returnObject;
    }

Answer 2

As this has been brought back up...

Here's an approach which uses some fairly standard utility functions to allow for a fairly simple implementation of your node reformatting and wraps that in a simple transformation of your whole forest of nodes. (It's not a tree, precisely, as there isn't a single root. This is commonly called a "forest".)

// utility functions
const groupBy = (fn) => (xs) => 
  xs .reduce ((a, x) => ({... a, [fn(x)]: [... (a [fn (x)] || []), x]}), {})
const mapObject = (fn) => (obj) =>
  Object .fromEntries (Object .entries (obj) .map (([k, v]) => [k, fn(v)]))

// helper functions
const hasKids = ({children = []}) => children .length > 0
const hasGrandkids = ({children = []}) => children .some (hasKids)

// main functions
const reformat = ({Id, children = []}) => ({
  ...(Id ? {Id} : {}), 
  ... mapObject (kids => kids .map (reformat)) (groupBy (o => o.Type) (children))
}) 

const transform = (nodes) => 
  nodes .filter (hasGrandkids) .map (reformat)

// sample data
const input = [{Type: "grdparent1", name: "grdparent1", children: [{Type: "grdparent1", Id: 45, children: []}, {Type: "grdparent1", Id: 46, children: [{Type: "parent1", Id: 54, children: [{Type: "child1", Id: 63, children: []}, {Type: "child2", Id: 64, children: []}]}, {Type: "parent2", Id: 57, children: []}]}]}, {Type: "grdparent2", name: "grdparent2", children: [{Type: "grdparent2", Id: 4, children: [{Type: "parent1", Id: 16, children: [{children: [], Type: "child1", Id: 28}]}, {Type: "parent2", Id: 17, children: []}]}]}, {Type: "grdparent3", name: "grdparent3", children: []}, {Type: "grdparent4", name: "grdparent4", children: [{Type: "parent1", Id: 167, children: []}]}]

// demo
console .log (transform (input))

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

The two important utility functions used are

• groupBy which groups an array into an object where the keys are generated by the supplied function mapped against the elements, and the values are arrays of the elements that generated that key. That is, for example,

  groupBy (({name}) => name[0]) ([
    {name: 'alice', age: 26}, 
    {name: 'bob', age: 19}, 
    {name: 'andrew', age: 31},
    {name: 'carol', age: 22}
  ])
  //=>
  // {
  //   a: [{name: 'alice', age: 26}, {name: 'andrew', age: 31}],
  //   b: [{name: 'bob', age: 19}],
  //   c: [{name: 'carol', age: 22}]
  // }
  

• and mapObject, which maps a function over the values of an object, for example,

  mapObject (n => n * n) ({a: 2, b: 3, c: 5, d: 7})
  //=> {a: 1, b: 4, c: 25, d: 49}
  

We also have two helper functions which simply determine whether the node has children and whether it has grandchildren. We will use this in transform, to choose only those nodes with grandchildren. And that, in fact, is all transform does: it filters the list of nodes to include only those with grandchildren, and then it calls our reformat function on each of them. (It's not at all clear to me that this is what was desired in the first place. The question title and text refer to searching for nodes, but there is no evidence in any code of actual searching taking place. I'm guessing here in a way that matches the sample output and at least one other answer. This part would be easy enough to refactor.)

reformat is the main function here, formatting a node and recurring on each of its children. This is a fairly tricky reformat, turning child Type names into object keys and including Id in the output only when it's present in the input.

But the code isn't that complex, thanks to the use of the two helper functions. We group the children by their Type property, and then on the resulting object, we use mapObject to apply kids => kids .map (reformat) to each node.

---

groupBy and mapObject are general-purpose utility functions, and there are equivalents in major libraries like Underscore, Lodash, and Ramda (disclaimer: I'm a Ramda principal team member). But these implementation show that it's fairly easy to maintain your own versions.

Answer 3

This really was an interesting question! Took me a while to figure it out :)

I'm not a big fan of reinventing the wheel. So I'd suggest you use a library. We like object-scan for data processing since it is very powerful once you wrap your head around it. Having said that, this question was tricky! Here is how you could solve it

// const objectScan = require('object-scan');

const data = [{ Type: 'grdparent1', name: 'grdparent1', children: [{ Type: 'grdparent1', Id: 45, children: [] }, { Type: 'grdparent1', Id: 46, children: [{ Type: 'parent1', Id: 54, children: [{ Type: 'child1', Id: 63, children: [] }, { Type: 'child2', Id: 64, children: [] }] }, { Type: 'parent2', Id: 57, children: [] }] }] }, { Type: 'grdparent2', name: 'grdparent2', children: [{ Type: 'grdparent2', Id: 4, children: [{ Type: 'parent1', Id: 16, children: [{ children: [], Type: 'child1', Id: 28 }] }, { Type: 'parent2', Id: 17, children: [] }] }] }, { Type: 'grdparent3', name: 'grdparent3', children: [] }, { Type: 'grdparent4', name: 'grdparent4', children: [{ Type: 'parent1', Id: 167, children: [] }] }];

const convert = (input) => {
  objectScan(['**[*]'], {
    breakFn: ({ isMatch, key, value, context }) => {
      if (isMatch) {
        context[key.length] = value.children.map(({ Type }) => Type);
      }
    },
    filterFn: ({ key, value, parent, property, context }) => {
      const result = 'Id' in value ? { Id: value.Id } : {};
      context[key.length].forEach((type, idx) => {
        result[type] = (result[type] || []).concat(value.children[idx]);
      });
      if (Object.keys(result).length === 0) {
        parent.splice(property, 1);
      } else {
        parent.splice(property, 1, result);
      }
    }
  })(input, []);
};

convert(data);

console.log(data);
// => [ { grdparent1: [ { Id: 45 }, { Id: 46, parent1: [ { Id: 54, child1: [ { Id: 63 } ], child2: [ { Id: 64 } ] } ], parent2: [ { Id: 57 } ] } ] }, { grdparent2: [ { Id: 4, parent1: [ { Id: 16, child1: [ { Id: 28 } ] } ], parent2: [ { Id: 17 } ] } ] }, { parent1: [ { Id: 167 } ] } ]

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

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

Note that the result matches the result of the currently accepted answer.