Issue in creating recursive JSON hierarchy tree

Question

I have input data in flatfile format. I have written my javascript code to create recursive hierarchy JSON tree. I am not getting expected tree (highlighted below as expected output). Can anyone please help me understand where I might be going wrong?

Note: In input data if there is no child_id it means it is leaf node.

Input data with code

var data=[
         {"Type":"Root","url":"abc","description":"Enterprise Risk Management Framework","id":0,"child_id":3},

{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":4},

{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":9},

{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":11},

{"Type":"Stem","url":"ghi","description":"Wholesale Credit Risk framework","id":4,"child_id":6},

{"Type":"Stem","url":"jkl","description":"Wholesale Credit Risk Policy","id":6,"child_id":7},

{"Type":"Stem","url":"jkl","description":"Wholesale Credit Risk Policy","id":6,"child_id":8},

{"Type":"Leaf","url":"mno","description":"Wholesale Credit In-Business Quality Assurance Standard","id":7},

{"Type":"Leaf","url":"pqr","description":"WCR Exception Management Standard","id":8},

{"Type":"Stem","url":"stu","description":"Global Collateral Management Policy","id":9,"child_id":10},

{"Type":"Leaf","url":"gov","description":"WCR Collateral Management Standard","id":10},

{"Type":"Stem","url":"iit","description":"Real Estate Appraisal and Valuation Policy","id":11,"child_id":12},

{"Type":"Stem","url":"iim","description":"Commercial Real Estate Appraisal/Valuation Standard","id":12,"child_id":13},

{"Type":"Leaf","url":"har","description":"Commercial Real Estate Appraisal/Valuation Procedures","id":13}
        ]



// Given a parent ID, find and return the item in the data with that ID
const findParent = parentId => data.find(item => item.child_id === parentId)

// Create the tree by reducing the data to a root list
// that only contains "orphans". Items that do have a
// parent will be appended to those orphans' child lists
// instead
const tree = data.reduce((root, item) => {
  // Find the parent of the current item
  const parent = findParent(item.id)

  if (parent) {
    // If a parent was found, append the current item
    // to the parent's child list. Since objects are
    // passed by reference, it doesn't matter whether 
    // the parent is already in the root list  or not 
    // -- it always points to the same object
    parent.children = parent.children || []
    parent.children.push(item)
  } else {
    // Otherwise push the item to the root list
    root.push(item)
  }

  return root
}, [])

console.log(JSON.stringify(tree));

Current Output

[
  {
    "Type": "Root",
    "url": "abc",
    "description": "Enterprise Risk Management Framework",
    "id": 0,
    "child_id": 3,
    "children": [
      {
        "Type": "Stem",
        "url": "def",
        "description": "Risk Governance Framework",
        "id": 3,
        "child_id": 4,
        "children": [
          {
            "Type": "Stem",
            "url": "mno",
            "description": "Wholesale Credit Risk Framework",
            "id": 4,
            "child_id": 6,
            "children": [
              {
                "Type": "Stem",
                "url": "pqr",
                "description": "Wholesale Credit Risk Policy",
                "id": 6,
                "child_id": 7,
                "children": [
                  {
                    "Type": "Leaf",
                    "url": "vwx",
                    "description": "Wholesale Credit In-Business Quality Assurance Standard",
                    "id": 7
                  }
                ]
              },
              {
                "Type": "Stem",
                "url": "stu",
                "description": "Wholesale Credit Risk Policy",
                "id": 6,
                "child_id": 8,
                "children": [
                  {
                    "Type": "Leaf",
                    "url": "zab",
                    "description": "WCR Exception Management Standard",
                    "id": 8
                  }
                ]
              }
            ]
          }
        ]
      },
      {
        "Type": "Stem",
        "url": "ghi",
        "description": "Risk Governance Framework",
        "id": 3,
        "child_id": 9,
        "children": [
          {
            "Type": "Stem",
            "url": "nsr",
            "description": "Global Collateral Management Policy",
            "id": 9,
            "child_id": 10,
            "children": [
              {
                "Type": "Leaf",
                "url": "gov",
                "description": "WCR Collateral Management Standard",
                "id": 10
              }
            ]
          }
        ]
      },
      {
        "Type": "Stem",
        "url": "jkl",
        "description": "Risk Governance Framework",
        "id": 3,
        "child_id": 11,
        "children": [
          {
            "Type": "Stem",
            "url": "iit",
            "description": "Real Estate Appraisal and Valuation Policy",
            "id": 11,
            "child_id": 12,
            "children": [
              {
                "Type": "Stem",
                "url": "iim",
                "description": "Commercial Real Estate Appraisal/Valuation Standard",
                "id": 12,
                "child_id": 13,
                "children": [
                  {
                    "Type": "Leaf",
                    "url": "har",
                    "description": "Commercial Real Estate Appraisal/Valuation Procedures",
                    "id": 13
                  }
                ]
              }
            ]
          }
        ]
      }
    ]
  }
]

expected Output

{
  "id": 0,
  "type": "Root",
  "description": "Enterprise Risk Management Framework",
  "url": "abc",
  "children": [
    {
      "id": 3,
      "type": "Stem",
      "description": "Risk Governance Framework",
      "url": "def",
      "children": [
        {
          "id": 4,
          "type": "Stem",
          "description": "Wholesale Credit Risk Framework",
          "url": "ghi",
          "children": [
            {
              "id": 6,
              "type": "Stem",
              "description": "Wholesale Credit Risk Policy",
              "url": "jkl",
              "children": [
                {
                  "id": 7,
                  "type": "Leaf",
                  "description": "Wholesale Credit In-Business Quality Assurance Standard",
                  "url": "mno",
                  "children": [
                    
                  ]
                },
                {
                  "id": 8,
                  "type": "Leaf",
                  "description": "WCR Exception Management Standard",
                  "url": "pqr",
                  "children": [
                    
                  ]
                }
              ]
            }
          ]
        },
        {
          "id": 9,
          "type": "Stem",
          "description": "Global Collateral Management Policy",
          "url": "stu",
          "children": [
            {
              "id": 10,
              "type": "Leaf",
              "description": "WCR Collateral Management Standard",
              "url": "gov",
              "children": [
                
              ]
            }
          ]
        },
        {
          "id": 11,
          "type": "Stem",
          "description": "Real Estate Appraisal and Valuation Policy",
          "url": "iit",
          "children": [
            {
              "id": 12,
              "type": "Stem",
              "description": "Commercial Real Estate Appraisal/Valuation Standard",
              "url": "iim",
              "children": [
                {
                  "id": 13,
                  "type": "Leaf",
                  "description": "Commercial Real Estate Appraisal/Valuation Procedures",
                  "url": "har",
                  "children": [
                    
                  ]
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

It looks like your code calls parent.children.push(item) for each item in data, and since you have multiple entries for a single node in your data array it is creating duplicates. Checking if a node already exists in the children array with the id prior to pushing a new entry would eliminate the duplicates. — davidgamero
– davidgamero, Commented Mar 10, 2022 at 19:54
@davidgamero The entries are not multiple but data is showing that the parent is same with multiple child. Look carefully, these have different child_id — Carpe Diem
– Carpe Diem, Commented Mar 10, 2022 at 19:58
i would recommend using an id lookup instead of iterating through the list as you traverse through the edges to build the tree similar to this answer — davidgamero
– davidgamero, Commented Mar 10, 2022 at 19:58
i see that there are 3 entries with id:3 and each has a different child_id 4,9,11, but the current code creates a new node with id:3 for each edge in the data list since it doesn't check if a node with id=3 already exists before adding it to the parent.children array — davidgamero
– davidgamero, Commented Mar 10, 2022 at 20:00
Thats what issue exist. I am breaking my head from past two weeks but not able to figure out how do I prevent creating new node and instead add it to existing. — Carpe Diem
– Carpe Diem, Commented Mar 10, 2022 at 20:04

trincot · Accepted Answer · 2022-05-03 12:28:33Z

3

You could collect the id and corresponding target object in a Map. Initially the children property of each object will be empty. Then iterate the data again to lookup the object for a given id and the object for the given child_id and put the latter object into the children array of the former. Finally, get the root object which is assumed to have id 0.

Code:

const data = [{"Type":"Root","url":"abc","description":"Enterprise Risk Management Framework","id":0,"child_id":3},{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":4},{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":9},{"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3,"child_id":11},{"Type":"Stem","url":"ghi","description":"Wholesale Credit Risk framework","id":4,"child_id":6},{"Type":"Stem","url":"jkl","description":"Wholesale Credit Risk Policy","id":6,"child_id":7},{"Type":"Stem","url":"jkl","description":"Wholesale Credit Risk Policy","id":6,"child_id":8},{"Type":"Leaf","url":"mno","description":"Wholesale Credit In-Business Quality Assurance Standard","id":7},{"Type":"Leaf","url":"pqr","description":"WCR Exception Management Standard","id":8},{"Type":"Stem","url":"stu","description":"Global Collateral Management Policy","id":9,"child_id":10},{"Type":"Leaf","url":"gov","description":"WCR Collateral Management Standard","id":10},{"Type":"Stem","url":"iit","description":"Real Estate Appraisal and Valuation Policy","id":11,"child_id":12},{"Type":"Stem","url":"iim","description":"Commercial Real Estate Appraisal/Valuation Standard","id":12,"child_id":13},{"Type":"Leaf","url":"har","description":"Commercial Real Estate Appraisal/Valuation Procedures","id":13}];

const map = new Map(data.map(({child_id, ...rest}) => [rest.id, {...rest, children: []}]));

for (const {id, child_id} of data) {
    if (!child_id) continue;
    const child = map.get(child_id);
    child.parentId = id;
    map.get(id).children.push(child);
}

console.log(map.get(0));

edited May 3, 2022 at 12:28

answered Mar 10, 2022 at 20:55

trincot

357k38 gold badges282 silver badges338 bronze badges

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

2 Comments

Carpe Diem Over a year ago

How can I bring parentId as attribute to children? For example "Type": "Stem", "url": "def", "description": "Risk Governance Framework", "id": 3, "parentId": 0

trincot Over a year ago

Updated to have parentId in output (when there is one). Can you update your question to have this requirement included? It is not currently in your "expected output" section.

James · Accepted Answer · 2022-03-10 20:55:42Z

Here's an example based on this answer. I have refactored your data to use id/parentId. I have removed the duplicates/not duplicates (you only really need 1 thing in the dataset per element of the tree, no matter how many children it has).

var data=[
  {"Type":"Root","url":"abc","description":"Enterprise Risk Management Framework","id":0},
  {"Type":"Stem","url":"def","description":"Risk Governance Framework","id":3, "parentId": 0},
  {"Type":"Stem","url":"ghi","description":"Wholesale Credit Risk framework","id":4, "parentId": 3},
  {"Type":"Stem","url":"jkl","description":"Wholesale Credit Risk Policy","id":6, "parentId": 4},
  {"Type":"Leaf","url":"mno","description":"Wholesale Credit In-Business Quality Assurance Standard","id":7, "parentId": 6},
  {"Type":"Leaf","url":"pqr","description":"WCR Exception Management Standard","id":8, "parentId": 6},
  {"Type":"Stem","url":"stu","description":"Global Collateral Management Policy","id":9, "parentId": 3},
  {"Type":"Leaf","url":"gov","description":"WCR Collateral Management Standard","id":10, "parentId": 9},
  {"Type":"Stem","url":"iit","description":"Real Estate Appraisal and Valuation Policy","id":11, "parentId": 3},
  {"Type":"Stem","url":"iim","description":"Commercial Real Estate Appraisal/Valuation Standard","id":12,"parentId":11},
  {"Type":"Leaf","url":"har","description":"Commercial Real Estate Appraisal/Valuation Procedures","id":13, "parentId": 12}
];
        
        
const createDataTree = dataset => {
  const map = {};
  dataset.forEach(aData => map[aData.id] = aData);
  const dataTree = [];
  dataset.forEach(d => {
    if (d.parentId !== undefined) {
      map[d.parentId].children = map[d.parentId].children || [];
      map[d.parentId].children.push(map[d.id]);
    } else {
      dataTree.push(map[d.id]);
    }
  });
  return dataTree;
};

const tree = createDataTree(data);
console.log(tree);

Collectives™ on Stack Overflow

Issue in creating recursive JSON hierarchy tree

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related