javascript - Recursive depth function on an array - Stack Overflow

admin管理员组

文章数量:1310034

I have an array of objects like this input, and I want to nest some objects inside another objects (based if their parentId is the parents' forumId),

I got the function working but up to 1 depth, how can I get it working for n depth? Any idea or optimizations are appreciated!

EDIT: After pointing out, the input isn't necessarily ordered.

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
  const topLevelForums = forumInput.filter(function (forum) {
    return forum.parentId === null;
  });

  let output = topLevelForums;

  forumInput.forEach(function (forum) {
    if (forum.parentId !== null) {
      const forumParentId = forum.parentId;
      output.forEach(function (parentForum, idx) {
        if (parentForum.forumId === forumParentId) {
          if (!output[idx].hasOwnProperty("subForums")) {
            output[idx].subForums = [];
          }
          parentForum.subForums.push(forum);
        }
      });
    }
  });

  return output;
}

This is the expected output:

[
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
    subForums: [
      {
        forumId: 2,
        parentId: 1,
        forumName: "Announcements",
        forumDescription: "Announcements & Projects posted here",
        forumLocked: false,
        forumDisplay: true,
      },
      {
        forumId: 3,
        parentId: 1,
        forumName: "General",
        forumDescription: "General forum, talk whatever you want here",
        forumLocked: false,
        forumDisplay: true,
        subForums: [
          {
            forumId: 4,
            parentId: 3,
            forumName: "Introduction",
            forumDescription: "A warming introduction for newers here",
            forumLocked: false,
            forumDisplay: true,
          },
        ],
      },
    ],
  },
]

This is the current output:

[
  {
    forumDescription: "",
    forumDisplay: true,
    forumId: 1,
    forumLocked: false,
    forumName: "Main",
    parentId: null,
    subForums: [
      {
        forumDescription: "Announcements & Projects posted here",
        forumDisplay: true,
        forumId: 2,
        forumLocked: false,
        forumName: "Announcements",
        parentId: 1,
      },
      {
        forumDescription: "General forum, talk whatever you want here",
        forumDisplay: true,
        forumId: 3,
        forumLocked: false,
        forumName: "General",
        parentId: 1,
      },
    ],
  },
]

I have an array of objects like this input, and I want to nest some objects inside another objects (based if their parentId is the parents' forumId),

I got the function working but up to 1 depth, how can I get it working for n depth? Any idea or optimizations are appreciated!

EDIT: After pointing out, the input isn't necessarily ordered.

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
  const topLevelForums = forumInput.filter(function (forum) {
    return forum.parentId === null;
  });

  let output = topLevelForums;

  forumInput.forEach(function (forum) {
    if (forum.parentId !== null) {
      const forumParentId = forum.parentId;
      output.forEach(function (parentForum, idx) {
        if (parentForum.forumId === forumParentId) {
          if (!output[idx].hasOwnProperty("subForums")) {
            output[idx].subForums = [];
          }
          parentForum.subForums.push(forum);
        }
      });
    }
  });

  return output;
}

This is the expected output:

[
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
    subForums: [
      {
        forumId: 2,
        parentId: 1,
        forumName: "Announcements",
        forumDescription: "Announcements & Projects posted here",
        forumLocked: false,
        forumDisplay: true,
      },
      {
        forumId: 3,
        parentId: 1,
        forumName: "General",
        forumDescription: "General forum, talk whatever you want here",
        forumLocked: false,
        forumDisplay: true,
        subForums: [
          {
            forumId: 4,
            parentId: 3,
            forumName: "Introduction",
            forumDescription: "A warming introduction for newers here",
            forumLocked: false,
            forumDisplay: true,
          },
        ],
      },
    ],
  },
]

This is the current output:

[
  {
    forumDescription: "",
    forumDisplay: true,
    forumId: 1,
    forumLocked: false,
    forumName: "Main",
    parentId: null,
    subForums: [
      {
        forumDescription: "Announcements & Projects posted here",
        forumDisplay: true,
        forumId: 2,
        forumLocked: false,
        forumName: "Announcements",
        parentId: 1,
      },
      {
        forumDescription: "General forum, talk whatever you want here",
        forumDisplay: true,
        forumId: 3,
        forumLocked: false,
        forumName: "General",
        parentId: 1,
      },
    ],
  },
]

• javascript
• arrays
• object
• recursion
• higher-order-functions

Share Improve this question Follow edited Jun 1, 2020 at 17:55 Stan Loona asked Jun 1, 2020 at 17:25 Stan LoonaStan Loona 70511 gold badge1010 silver badges2222 bronze badges 2

• In input, the parent forum id always before its children. Will that always be true? Or can it be that a parent appears after its children in that array? – T.J. Crowder Commented Jun 1, 2020 at 17:34
• @T.J.Crowder not ordered, they can appear randomly – Stan Loona Commented Jun 1, 2020 at 17:47

Add a ment  | 

6 Answers 6

Sorted by: Reset to default 6

A wonderful opportunity to learn about mutual recursion. The input can be in any order -

function makeIndex (items, indexer)
{ const append = (r, k, v) =>
    r.set(k, (r.get(k) || []).concat([ v ]))

  return items.reduce
    ( (r, i) => append(r, indexer(i), i)
    , new Map
    )
}

function makeTree (index, root = null)
{ const many = (all = []) =>
    all.map(one)

  const one = (forum = {}) =>
    ( { ...forum
      , subforums: many(index.get(forum.forumId))
      }
    )

  return many(index.get(root))
}

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newers here",forumLocked:false,forumDisplay:true}]

const result =
  makeTree(makeIndex(input, forum => forum.parentId))

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

[
  {
    "forumId": 1,
    "parentId": null,
    "forumName": "Main",
    "forumDescription": "",
    "forumLocked": false,
    "forumDisplay": true,
    "subforums": [
      {
        "forumId": 2,
        "parentId": 1,
        "forumName": "Announcements",
        "forumDescription": "Announcements & Projects posted here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": []
      },
      {
        "forumId": 3,
        "parentId": 1,
        "forumName": "General",
        "forumDescription": "General forum, talk whatever you want here",
        "forumLocked": false,
        "forumDisplay": true,
        "subforums": [
          {
            "forumId": 4,
            "parentId": 3,
            "forumName": "Introduction",
            "forumDescription": "A warming introduction for newers here",
            "forumLocked": false,
            "forumDisplay": true,
            "subforums": []
          }
        ]
      }
    ]
  }
]

---

make it modular

Above makeIndex is written in a way that it can index any array of datum, but makeTree makes assumptions like ...forum, subforums, and forum.forumId. When we think about our code in modules, we are forced to draw lines of separation and consequently our programs bee untangled.

Below, input is defined in main and so we keep all knowledge about input here -

// main.js
import { tree } from './tree'

const input =
  [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newers here",forumLocked:false,forumDisplay:true}]

const result =
  tree
    ( input                    // <- array of nodes
    , forum => forum.parentId  // <- foreign key
    , (forum, subforums) =>    // <- node reconstructor function
        ({ ...forum, subforums: subforums(forum.forumId) }) // <- primary key
    )

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

When I make a tree, I don't want to have to think about making an index first. In our original program, how was I supposed to know a tree needed an index? Let's let the tree module worry about that -

// tree.js
import { index } from './index'

const empty =
  {}

function tree (all, indexer, maker, root = null)
{ const cache =
    index(all, indexer)

  const many = (all = []) =>
    all.map(x => one(x))
                             // zero knowledge of forum object shape
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

export { empty, tree } // <-- public interface

We could have written the index function directly in the tree module but the behavior we want is not specific to trees. Writing a separate index module makes more sense -

// index.js
const empty = _ =>
  new Map

const update = (r, k, t) =>
  r.set(k, t(r.get(k)))

const append = (r, k, v) =>
  update(r, k, (all = []) => [...all, v])

const index = (all = [], indexer) =>
  all.reduce
      ( (r, v) => append(r, indexer(v), v) // zero knowledge of v shape
      , empty()
      )

export { empty, index, append } // <-- public interface

Writing modules helps you think about your code in meaningful parts and promotes a high degree of code reusability.

It's been a while since this has been asked, but since the accepted answer has been linked in another question and I find it too plex, I'll add my answer here as well:

• Keeping it abstract enough to deal with arbitrary trees? OK, fine.
• Random order of parents/children in the input? Sure, why not.
• And on top of that, in a single sweep over the input array

function makeTree(input, indexer, maker, root = null) {
  const cache = new Map;
  // get or create (and return) children array for the passed key;
  const getChildrenArray = key => cache.get(key) || cache.set(key, []).get(key);

  for (let item of input) {
    getChildrenArray(indexer(item)).push(
      maker(item, getChildrenArray)
    );
  }
  
  return cache.get(root);
}

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function makeTree(input, indexer, maker, root = null) {
  const cache = new Map;
  // get or create (and return) children array for the passed key;
  const getChildrenArray = key => cache.get(key) || cache.set(key, []).get(key);

  for (let item of input) {
    getChildrenArray(indexer(item)).push(
      maker(item, getChildrenArray)
    );
  }
  
  return cache.get(root);
}

const result = makeTree(
  input,
  item => item.parentId,
  (item, getChildrenFor) => ({ 
    ...item, 
    subForums: getChildrenFor(item.forumId) 
  }),
  null
);

console.log(result);

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

Since parents might be after the children in the input, I think I'd approach it by building a Map of forums by ID, then adding the children to them:

function processInput(forumInput) {
    // Get a map of forums by ID
    const forumsById = new Map();
    for (const forum of forumInput) {
        forumsById.set(forum.forumId, forum);
    }

    // Add child forums to their parents
    for (const forum of forumInput) {
        const {parentId} = forum;
        if (parentId !== null) {
            const parent = forumsById.get(forum.parentId);
            parent.subForums = parent.subForums || []; // Or you could use `?? []` now
            parent.subForums.push(forum);
        }
    }

    // Return the parents array
    return [...forumsById.values()].filter(({parentId}) => parentId === null);
}

Live Example:

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

function processInput(forumInput) {
    // Get a map of forums by ID
    const forumsById = new Map();
    for (const forum of forumInput) {
        forumsById.set(forum.forumId, forum);
    }

    // Add child forums to their parents
    for (const forum of forumInput) {
        const {parentId} = forum;
        if (parentId !== null) {
            const parent = forumsById.get(forum.parentId);
            parent.subForums = parent.subForums || []; // Or you could use `?? []` now
            parent.subForums.push(forum);
        }
    }

    // Return the parents array
    return [...forumsById.values()].filter(({parentId}) => parentId === null);
}

console.log(processInput(input));

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

Note that the above will throw an error if a forum claims to be in a parent forum that isn't in the input.

I think the systematic approach is 1. create a map of id to object 2. create a map of parent -> children 3. add all the parent to the results 4. recursively add children (subforums)

const input = [
  {
    forumId: 1,
    parentId: null,
    forumName: "Main",
    forumDescription: "",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 2,
    parentId: 1,
    forumName: "Announcements",
    forumDescription: "Announcements & Projects posted here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 3,
    parentId: 1,
    forumName: "General",
    forumDescription: "General forum, talk whatever you want here",
    forumLocked: false,
    forumDisplay: true,
  },
  {
    forumId: 4,
    parentId: 3,
    forumName: "Introduction",
    forumDescription: "A warming introduction for newers here",
    forumLocked: false,
    forumDisplay: true,
  },
];

const mapIdToForums = input.reduce((acc, cur) => {
  acc[cur.forumId] = cur;
  return acc;
}, {});

const mapForumsToSubForums = input.reduce((acc, cur) => {
  parentId = cur.parentId || ""; // no parent
  acc[parentId] = acc[parentId] || [];
  acc[parentId].push(cur);
  return acc;
}, {});


const addChildren = (parent) => {
  var children = mapForumsToSubForums[parent.forumId];
  if (children) {
    parent.subForums = children

    children.forEach(c => addChildren(c));
  }
};

results = mapForumsToSubForums[""];
results.forEach(p => addChildren(p));
console.log(results);

You could take an object which takes all relation from an object with child to parent and parent to childand get the nodes which have no parent.

This approach works for any depth, unsorted data and uses only a single loop.

const
    input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }],
    tree = function(data, root) {
        var t = {};
        data.forEach(o => {
            Object.assign(t[o.forumId] = t[o.forumId] || {}, o);
            t[o.parentId] = t[o.parentId] || {};
            t[o.parentId].subForums = t[o.parentId].subForums || [];
            t[o.parentId].subForums.push(t[o.forumId]);
        });
        return t[root].subForums;
    }(input, null);

console.log(tree);

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

As some other answers, I would use a Map to key nodes by their forumId, and then populate the children inside the corresponding values:

let input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }];

let root = {};
let map = new Map(input.map(o => [o.forumId, ({...o})]))
map.forEach(o => (p => p.subForms = (p.subForms || []).concat(o))(map.get(o.parentId) || root));
let result = root.subForms;

console.log(result);

本文标签： javascriptRecursive depth function on an arrayStack Overflow