How to recursively merge the same node elements of a JSON tree

Question

How to gather the same parent elements of a tree in a nested way. I have a JSON array with different nesting levels. I have this:

  var jsonArray = [
{
  label: 'Parent 1',
  id: '26',
  children: [
    {
      label: 'child 11',
      id: '139',
      children: [
        {
          label: 'child 111',
          id: '558',
          children: [
            {
              label: 'child 1111',
              id: '1420',
            },
          ],
        },
      ],
    },
  ],
},
{
  label: 'Parent 2',
  id: '24',
  children: [
    {
      label: 'child 21',
      id: '140',
      children: [
        {
          label: 'child 211',
          id: '142',
          children: [
            {
              label: 'child 2111',
              id: '4394',
            },
          ],
        },
      ],
    },
  ],
},
{
  label: 'Parent 3',
  id: '154',
  children: [
    {
      label: 'child 31',
      id: '161',
      children: [
        {
          label: 'child 311',
          id: '260',
          children: [
            {
              label: 'child 3111',
              id: '1837',
            },
          ],
        },
      ],
    },
  ],
},
{
  label: 'Parent 1',
  id: '26',
  children: [
    {
      label: 'child 11',
      id: '139',
      children: [
        {
          label: 'child 112',
          id: '470',
          children: [
            {
              label: 'child 1121',
              id: '957',
            },
          ],
        },
      ],
    },
  ],
},

];

I want merging JSON elements with the same parent, and check if their children have the same values, like this:

[
    {
      label: 'Parent 1',
      id: '26',
      children: [
        {
          label: 'child 11',
          id: '139',
          children: [
            {
              label: 'child 111',
              id: '558',
              children: [
                {
                  label: 'child 1111',
                  id: '1420',
                },
              ],
            },
            {
              label: 'child 112',
              id: '470',
              children: [
                {
                  label: 'child 1121',
                  id: '957',
                },
              ],
            },
          ],
        },
      ],
    },
    {
      label: 'Parent 2',
      id: '24',
      children: [
        {
          label: 'child 21',
          id: '140',
          children: [
            {
              label: 'child 211',
              id: '142',
              children: [
                {
                  label: 'child 2111',
                  id: '4394',
                },
              ],
            },
          ],
        },
      ],
    },
    {
      label: 'Parent 3',
      id: '154',
      children: [
        {
          label: 'child 31',
          id: '161',
          children: [
            {
              label: 'child 311',
              id: '260',
              children: [
                {
                  label: 'child 3111',
                  id: '1837',
                },
              ],
            },
          ],
        },
      ],
    }
  ];

I use the primeng-tree component to display this tree

Here a stackblitz demo

Thank's

score 1 · Accepted Answer · answered Jul 28 '22 at 23:11

Here's one solution using Maps and Sets

type Person = {
  label: string;
  id: string;
  children?: Person[];
};

  jsonArray: Person[] = [ ... ]

  ngOnInit() {
    this.tree = this.sort(this.jsonArray);
  }

  sort(people: Person[]) {
    const cMap = new Map<string, Set<string>>(); // <parent id, Set<child id>>
    const pMap = new Map<string, Person>(); // people by id
    const topLevelIds = new Set<string>(); // people that have no parents
    // populate collections
    for (const person of people) {
      topLevelIds.add(person.id);
      this.mergePerson(person, pMap, cMap);
    }
    // put children into person map
    for (const [id, parent] of pMap.entries()) {
      const children = cMap.get(id);
      for (const id of children.values()) {
        const child = pMap.get(id);
        parent.children!.push(child);
      }
    }
    // create array
    const res = [];
    for (const id of topLevelIds.values()) res.push(pMap.get(id));
    return res;
  }

  mergePerson(
    p: Person,
    pMap: Map<string, Person>,
    cMap: Map<string, Set<string>>
  ) {
    if (!pMap.get(p.id)) pMap.set(p.id, { ...p, children: [] });
    if (!cMap.get(p.id)) cMap.set(p.id, new Set());
    if (!p.children) return;
    const children = cMap.get(p.id);
    for (const child of p.children) {
      children.add(child.id);
      this.mergePerson(child, pMap, cMap);
    }
  }

Stackblitz: https://stackblitz.com/edit/primeng-tree-demo-9stkkw?file=src/app/app.component.ts

I found a bug in this solution, when the parent has the same id as a child, it reproduces a bug, the child becomes parent. — medah, Aug 08 '22 at 15:24
I don't understand, if a child and a parent have the same id, this represents one node that is both a parent and a child. I assumed that an id denotes a unique node. By your comment it sounds like you have nodes with the same id, but different labels. That kind of defeats the purpose of an id. — Chris Hamilton, Aug 08 '22 at 17:55
yes because each level is an entity in the database :) if we add for example a "type" property for each level it can solve that? — medah, Aug 08 '22 at 19:55

How to recursively merge the same node elements of a JSON tree

1 Answers1