JS Recursion Algo problem with positioning elements into correct order

Question

I have a problem that I have been racking my head on and seem to be stuck. I have an array of entities that I need to sort but also nest within one another if the condition is met. They also need to be sorted by count within their own scope.

let entity = {
  company: {id: string, parent_id?: string, count: number}
}

let arr = entity[]

What I need to do is loop through the array and see which entities are children of other entities and nest them accordingly. So as an example

let arr = [{company: {id: 1, count: 10}}, {company: {id: 2, parent_id: 1, count: 3}}, {company:{id: 3: parent_id: 1, count: 5}}, {company: {id: 4, parent_id: 2, count: 4}}, {company: {id: 5, count: 1}]

After computation this should be:

[
  {company: {
    id: 1, 
    count: 10, 
    children: [
      {company: {
        id: 3,
        parent_id: 1,
        count: 5
      }},
      {company: {
        id: 2,
        parent_id: 1
        count: 3,
        children: [
          {company: {
            id: 4,
            parent_id: 2,
            count: 4
          }
        ]
      }}
    ]
  }},
  {company: {
    id: 5, count: 1
  }}
]

I essentially need to "unflatten" the map, I have tried some recursive strategies like saving to a set the initial entities and then looping through the initial array and trying to nest/remove entities as needed, but havent found success so far. Any help would be appreciated.

Answer 1

Here's a concept, with lodash as the only dependency (both _.keyBy and _.sortBy can easily be written in pure javascript).

It breaks down the problem in two steps: first nesting, second recursively sorting entities.

It edits the original arguments, you can do _.cloneDeep to keep the input unchanged.

import _ from "lodash";

type Company = {id: string, parent_id?: string, count: number};
type Entity = {company: Company};
type NestedEntity = {company: Company & {children?: NestedEntity[]}};

// entities is the input

const entities_by_id = _.keyBy(entities, 'company.id');

// This is the output
let results: NestedEntity [] = [];

// Step 1: nest entities
for (const entity of entities) {
  if (entity.company.parent_id) {
    const parent = entities[company.parent_id];
    parent.company.children = parent.company.children ?? [];
    parent.company.children.push(entity);
  } else {
    results.push(entity);
  }
}

//Step 2: sort recursively
function sortEntities(entityArray) {
  const sorted = _.sortBy(entityArray, "company.count").reverse();

  for (const entity of sorted) {
    if (entity.company.children) {
      entity.company.children = sortEntities(entity.company.children);
    }
  }

  return sorted;
}

results = sortEntities(results);

Answer 2

You could take a single loop approach without using libraries.

This approach takes this node and the parent node (this virtually only with children) and builds a nested tree.

At the end, the root node companie's children are returned.

const
    getTree = (data, root) => {
        const
            getLeaf = (object, keys, last = {}) =>
                keys.reduce((o, k, i, { length }) =>
                    o[k] = o[k] || (i + 1 === length ? last : {}), object),
            t = {};

        data.forEach(({ company }) => {
            Object.assign(getLeaf(t, [company.id, 'company']), company);
            getLeaf(t, [company.parent_id, 'company', 'children'], [])
                .push(t[company.id]);
        });

        return t[root].company.children;
    },
    data = [{ company: { id: 1, count: 10 } }, { company: { id: 2, parent_id: 1, count: 3 } }, { company: { id: 3, parent_id: 1, count: 5 } }, { company: { id: 4, parent_id: 2, count: 4 } }, { company: { id: 5, count: 1 } }],
    tree = getTree(data);

console.log(tree);

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

Answer 3

I recently wrote an answer that tries to solve such problems generically. (Most of this is in the Update in that answer.) While this is a slight tweak from that, as I'm still fiddling, it should solve the problem reasonably well:

// generic solution
const forest = (build, isChild, root) => (xs) => 
  xs .filter (x => isChild (root, x))
     .map (node => build (node, root => forest (build, isChild, root) (xs)))
    
// comparator for sorting
const byCountDesc = ({company: {count: a = 0}}, {company: {count: b = 0}}) => b - a

// customization for input structure.
const transform = (xs) => forest (
  (x, f) => ({company: {...x.company, children: f(x .company .id) .sort (byCountDesc)}}),
  (id, {company: {parent_id}}) => parent_id == id,
  null
) (xs) .sort (byCountDesc)


// sample data
const arr = [{company: {id: 1, count: 10}}, {company: {id: 2, parent_id: 1, count: 3}}, {company: {id: 3, parent_id: 1, count: 5}}, {company: {id: 4, parent_id: 2, count: 4}}, {company: {id: 5, count: 1}}]

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

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

The first parameter to forest is a function that accepts an element and a function that will be called on a reference to the element (for us it's the element's id, but see that answer for other possibilities) to return a substructure. Our function will build out the current node, by making a near-clone of the original with a children property pointing to the result of calling the function, passing the id.

The second parameter tells us if one node is the child of another. Here's its just matching the id with a parent_id.

The third parameter is the root value, null in our case because elements with no parent have no parent_id. Other circumstances might have 0 or some other dedicated id. And there are other possibilities as discussed there.

forest then returns a function which takes your flat array and restructures it as desirred.

If you mind having empty children nodes here and there, then we could replace the customized function with

const transform = forest (
  (x, f, kids = f(x.company.id)) => ({
    company: {...x.company, ...(kids.length ? {children: kids} : {})}
  }),
  (id, {company: {parent_id}}) => parent_id == id,
  null
)

For another generic approach, using similar arguments, but a different design, see the answer from Thankyou in that same question.

Answer 4

You can use a map to key your objects by their id, and then iterate them to add them to the children list of their parent. A temporary root object helps to collect the result array:

let arr = [{company: {id: 1, count: 10}}, {company: {id: 2, parent_id: 1, count: 3}}, {company: {id: 3, parent_id: 1, count: 5}}, {company: {id: 4, parent_id: 2, count: 4}}, {company: {id: 5, count: 1}}];

let result = [], root = { children: result };
let map = new Map(arr.map(({company}) => [company.id, {company:{...company}}]));
for (let o of map.values()) {
    ((map.get(o.company.parent_id)?.company || root).children ||= []).push(o);
}

console.log(result);

Answer 5

A great opportunity to learn about reusable modules and mutual recursion. This solution in this answer solves your specific problem without any modification of the modules written in other answers.

---

First, to solve the sorting portion of the problem we will compare by count using the Comparison module, presented in this Q&A. If this feels strange to you, check out the post to see a wide variety of ways in which the module is useful -

import * as Comparison from "./Comparison"

const byCount =
  Comparison.map                            // map a comparison
    ( Comparison.desc                       // default "descending" comparison
    , ({ company: { count = 0 }}) => count  // path to count property
    )

// ...

Second, to build the required tree using the Tree module, presented in this Q&A -

// ...

import { tree } from "./Tree"

const foreignKey = ({ company: { parent_id }}) =>
  parent_id

const input =
  [{company: {id: 1, count: 10}}, {company: {id: 2, parent_id: 1, count: 3}}, {company: {id: 3, parent_id: 1, count: 5}}, {company: {id: 4, parent_id: 2, count: 4}}, {company: {id: 5, count: 1}}]

const result =
  tree
    ( input
    , foreignKey        // <- your foreign key
    , (node, get) =>
        ( { ...node
          , children:
              get(node.company.id) // <- your primary key
                .sort(byCount)  // <- sort children
          }
        )
    )
    .sort(byCount) // <- sort root elements

console.log(JSON.stringify(result, null, 2))

Output; sibling nodes are sorted by count in descending order -

[
  {
    "company": {
      "id": 1,
      "count": 10
    },
    "children": [
      {
        "company": {
          "id": 3,
          "parent_id": 1,
          "count": 5
        },
        "children": []
      },
      {
        "company": {
          "id": 2,
          "parent_id": 1,
          "count": 3
        },
        "children": [
          {
            "company": {
              "id": 4,
              "parent_id": 2,
              "count": 4
            },
            "children": []
          }
        ]
      }
    ]
  },
  {
    "company": {
      "id": 5,
      "count": 1
    },
    "children": []
  }
]

---

branching implementations

@ScottSauyet makes me consider alternate designs for tree, especially considering renaming it to forest. One particular improvement I had in mind was to make tree simply take a pair of primary and foreign keys along with a child transform function -

// Main.js

const input =
  // ...

const byCount =
  // ...

const fk = ({ company: { parent_id }}) =>
  parent_id

const pk = ({ company: { id }}) =>
  id

const result =
  tree
    ( input
    , [ pk, fk ] // <- primary/foreign key pair
    , children => ({ children: children.sort(byCount) }) // <- transform
    )
    .sort(byCount)

console.log(JSON.stringify(result, null, 2))

The result is valid of course, so long as we update tree to make it so! -

// Tree.js (revised)

function tree (all, [pk, fk], maker, root)   // <-
{ const cache =
    index(all, fk)

  const many = (all = []) =>
    all.map(x => one(x))
    
  const one = (single) =>
    ({ ...single, ...maker(many(cache.get(pk(single)))) }) // <-

  return many(cache.get(root))
}

One downside to this is single and (return value of) maker are assumed to be objects, {...}, and so it restricts some of the tree shapes you can build. A more sophisticated merge could use runtime type-checking but I'm wary to go down that path. Another downside is all properties of node are included in the result whereas before we could pick all/any/none.