Create tree structure from array of objects with recursion or loop-CodePudding

Here we have two main properties, "ID" and "FatherOrganizationID". We need to make a tree where if fatherOranizationId === null -> must be at the top, and if the fatherOrganizationId !== null, it must be in subOrganizations array of items that have ID === FatherOrganizationID. Can someone help with it? Must work in any depth. I know that it is able with recursion but have no mind how to realize it

START DATA:

{
  "id": 1000,
  "organizationName": "testOrg1",
  "fatherOrganizationId": null,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1001,
  "organizationName": "testOrg2",
  "fatherOrganizationId": 1000,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1002,
  "organizationName": "testOrg3",
  "fatherOrganizationId": 1001,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1003,
  "organizationName": "testOrg4",
  "fatherOrganizationId": 1001,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1004,
  "organizationName": "testOrg7",
  "fatherOrganizationId": 1001,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1005,
  "organizationName": "testOrg7",
  "fatherOrganizationId": 1002,
  "subOrganizations": [],
  "isActive": false,
},
{
  "id": 1006,
  "organizationName": "testOrg8",
  "fatherOrganizationId": null,
  "subOrganizations": [],
  "isActive": false,
}

EXPECTED RESULT:

[
{
  "id": 1000,
  "organizationName": "testOrg1",
  "fatherOrganizationId": null,
  "subOrganizations": [
    {
      "id": 1001,
      "organizationName": "testOrg2",
      "fatherOrganizationId": 1000,
      "subOrganizations": [
        {
          "id": 1002,
          "organizationName": "testOrg3",
          "fatherOrganizationId": 1001,
          "subOrganizations": [
            {
              "id": 1005,
              "organizationName": "testOrg7",
              "fatherOrganizationId": 1002,
              "subOrganizations": [],
              "isActive": false,
            }
          ],
          "isActive": false,
        },
        {
          "id": 1003,
          "organizationName": "testOrg4",
          "fatherOrganizationId": 1001,
          "subOrganizations": [],
          "isActive": false,
        },
        {
          "id": 1004,
          "organizationName": "testOrg7",
          "fatherOrganizationId": 1001,
          "subOrganizations": [],
          "isActive": false,
        },
      ],
      "isActive": false,
    },
  ],
  "isActive": false,
},
{
  "id": 1006,
  "organizationName": "testOrg8",
  "fatherOrganizationId": null,
  "subOrganizations": [],
  "isActive": false,
}     
]

CodePudding user response：

I wrote this code snippet in Typescript, but the concept is the same in C#. It's by no means the fastest algorithm to do this, but it's simple and readable:

type OrgType = {
    id: number;
    organizationName: string;
    fatherOrganizationId: number;
    subOrganizations: OrgType[];
    isActive: boolean;
}

const orgListFromData = JSON.parse(readFileSync("./data.json", 'utf-8')).list as OrgType[];

/**
 * populate organization object 
 * with child organizations 
 */
const populateOrgWithChildren = (organizationsList: OrgType[], organization: OrgType): OrgType => {

    /**
     * get sub organizations, with their subOrganizations already populated,
     * - gets recursive here -
     */
    const subOrganizations = organizationsList
        .filter(org => org.fatherOrganizationId === organization.id)
        .map(org => populateOrgWithChildren(organizationsList, org));

    /**
     * create a new object and spread properties from original, 
     * to avoid mutating original object trough this mem referenence 
     */
    return {
        ...organization,
        subOrganizations
    }
}

/**
 * populate a list of organizations with
 * their child organizations 
 */
const populateOrgs = (organizationsList: OrgType[]) => {

    const rootOrgs = organizationsList
        .filter(x => x.fatherOrganizationId === null);


    const populatedRootOrgs = rootOrgs
        .map(rootOrg => populateOrgWithChildren(organizationsList, rootOrg));

    return populatedRootOrgs;
}

/**
 * Results
 */
const populated = populateOrgs(orgListFromData);

Hope it helps. Tested it myself, works fine. Something that you might want to pay attention to, is that this task is split in 2 parts: you want to find the "root" organizations, and you want to create a hierarchical structure of the rest of the organizations. This is why I split the code into 2 funcitons, populateOrgWithChildren and populateOrgs. The first being the recursive function that can organize the organizations into a tree under a root organization. The second being the function that finds all the root organizations.

Another solution might be to preprocess your data, and assign every organization with null parent id a parent id of let's say -1, and add a new node called "root" with the id -1. (- to denote that it's not a real id from the DB). After this, you can run only the populateOrgWithChildren on the node that has -1 as it's id, since the whole tree will be of the same structure, there's not going to be null id's anywhere. The resut would be a tree that starts with a single root node, which has a made up id, and all the other organizations would rest under that node.

A little help: TS's .filter() equals to C# (LINQ's) .Where().