How to create a new object from parent/child relationships using recursive JavaScript map method

Question

I've got an array of objects. Some of them have a wordpress_parent prop with a value `. This means this node is a child of another node. The actual end result is a nested comment UI, so there can be multiple levels of children.

I'd like to loop through my objects and where wordpress_parent !== 0, find the object in the original array whose wordpress_id equals the value of wordpress_parent and put that object as a child property of the matching parent node.

I want to achieve this object form:

node {
    ...originalPropsHere,
    children: { ...originalChildNodeProps } 
}

The idea is to create a new array with the proper nested structure of parent, children that I can then iterate over and pump out into a JSX structure.

I want to write a recursive function that does this logic and then returns a JSX comment structure like this (basically):

<article className="comment" key={node.wordpress_id}>
    <header>
        <a href={node.author_url} rel="nofollow"><h4>{node.author_name}</h4></a>
        <span>{node.date}</span>
    </header>
    {node.content}
</article>

I figure I have to use JavaScripts' map method to create a new array. The trouble I'm having is manipulating the data to create a new children property on my parent nodes, then placing the matching child comment as the value of that property. Then placing that in a nice little function that recursively goes through and creates the HTML/JSX structure that I can render in my components.

Smarter folks, step right up please, and thank you! :D

Answer 1

This is a modification of another answer, which handles the extra node wrapper and your id and parent property names:

const nest = (xs, id = 0) => 
  xs .filter (({node: {wordpress_parent}}) => wordpress_parent == id)
     .map (({node: {wordpress_id, wordpress_parent, ...rest}}) => ({
       node: {
         ...rest,
         wordpress_id, 
         children: nest (xs, wordpress_id)
       }
     }))

const edges = [
  {node: {content: 'abc', wordpress_id: 196, wordpress_parent: 193}},
  {node: {content: 'def', wordpress_id: 193, wordpress_parent: 0}},
  {node: {content: 'ghi', wordpress_id: 199, wordpress_parent: 193}},
  {node: {content: 'jkl', wordpress_id: 207, wordpress_parent: 0}},
  {node: {content: 'mno', wordpress_id: 208, wordpress_parent: 207}},
  {node: {content: 'pqr', wordpress_id: 209, wordpress_parent: 208}},
  {node: {content: 'stu', wordpress_id: 224, wordpress_parent: 207}}
]

console .log (
  nest (edges)
)

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

It includes an empty children array in those nodes without children. (If you know that you can only have at most one child and prefer the name child, then this would take a little reworking; but it shouldn't be bad.)

Basically, it takes a list of items and an id to test, and filters the list for those that have that id. Then it adds a children property by recursively calling the function with the id of the current object.

Because wordpress_parent is included in the destructured parameters for the function passed to map but not included in the output, this node is skipped. If you want to keep it, you could add it to the output, but even easier is skipping it as a parameter; then it will be part of ...rest.

Update: Generalization

The answer from Thankyou is inspirational. I've answered quite a few questions like this with variants of the same answer. It's past time to generalize to a reusable function.

That answer creates an index of all values and then builds the output using the index. My technique above (and in several other answers) is somewhat different: scanning the array for all root elements and, for each one, scanning the array for their children, and, for each of those, scanning the array for the grandchildren, etc. This is probably less efficient, but is slightly more easily generalized, as there is no need to generate a representative key for each element.

So I've created a first pass at a more general solution, in which what I do above is separated out into two simpler functions which are passed (along with the original data and a representation of the root value) into a generic function which puts those together and handles the recursion.

Here's an example of using this function for the current problem:

// forest :: [a] -> (a, (c -> [b]) -> b) -> ((c, a) -> Bool) -> c -> [b]
const forest = (xs, build, isChild, root) => 
  xs .filter (x => isChild (root, x))
     .map (node => build (node, root => forest (xs, build, isChild, root)))
    
const edges = [{node: {content: 'abc', wordpress_id: 196, wordpress_parent: 193}}, {node: {content: 'def', wordpress_id: 193, wordpress_parent: 0}}, {node: {content: 'ghi', wordpress_id: 199, wordpress_parent: 193}}, {node: {content: 'jkl', wordpress_id: 207, wordpress_parent: 0}}, {node: {content: 'mno', wordpress_id: 208, wordpress_parent: 207}}, {node: {content: 'pqr', wordpress_id: 209, wordpress_parent: 208}}, {node: {content: 'stu', wordpress_id: 224, wordpress_parent: 207}}]

const result = forest (
  edges,     
  (x, f) => ({node: {...x.node, children: f (x.node.wordpress_id)}}),
  (id, {node: {wordpress_parent}}) => wordpress_parent == id,
  0
)

console .log (result)

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

I use forest rather than tree, as what's generated here is not actually a tree. (It has multiple root nodes.) But its parameters are very similar to those from Thankyou. The most complex of them, build is exactly equivalent to that answer's maker. xs is equivalent to all, and the root parameters are (nearly) equivalent. The chief difference is between Thankyou's indexer and my isChild. Because Thankyou generates a Map of foreign keys to elements, indexer takes a node and returns a representation of the node, usually a property. My version instead is a binary predicate. It takes a representation of the current element and a second element and returns true if and only if the second element is a child of the current one.

Different styles of root parameter

The final parameter, root, is actually fairly interesting. It needs to be some sort of representative of the current object. But it does not need to be any particular representative. In simple cases, this can just be something like an id parameter. But it can also be the actual element. This would also work:

console .log (forest (
  edges,
  (x, f) => ({node: {...x.node, children: f (x)}}),
  (p, c) => p.node.wordpress_id == c.node.wordpress_parent,
  {node: {wordpress_id: 0}}
))

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

<script>const forest = (xs, build, isChild, root) => xs .filter (x => isChild (root, x)).map (node => build (node, root => forest (xs, build, isChild, root)))
        const edges = [{node: {content: 'abc', wordpress_id: 196, wordpress_parent: 193}}, {node: {content: 'def', wordpress_id: 193, wordpress_parent: 0}}, {node: {content: 'ghi', wordpress_id: 199, wordpress_parent: 193}}, {node: {content: 'jkl', wordpress_id: 207, wordpress_parent: 0}}, {node: {content: 'mno', wordpress_id: 208, wordpress_parent: 207}}, {node: {content: 'pqr', wordpress_id: 209, wordpress_parent: 208}}, {node: {content: 'stu', wordpress_id: 224, wordpress_parent: 207}}]</script>

In this case, the final parameter is more complex, being an object structurally similar to a typical element in the list, in this case with the root id. But when we do this, the parameters isChild and to the callback supplied by build are a bit simpler. The thing to keep in mind is that this is the structure passed to isChild. In the first example that was just the id, so the root parameter was simple, but those other functions were a bit more complex. In the second one, root was more complex, but it allowed us to simplify the other parameters.

Other transformations

This can easily be applied to other examples. The earlier question mentioned before can be handled like this:

const flat = [
  {id: "a", name: "Root 1", parentId: null}, 
  {id: "b", name: "Root 2", parentId: null}, 
  {id: "c", name: "Root 3", parentId: null}, 
  {id: "a1", name: "Item 1", parentId: "a"}, 
  {id: "a2", name: "Item 1", parentId: "a"}, 
  {id: "b1", name: "Item 1", parentId: "b"}, 
  {id: "b2", name: "Item 2", parentId: "b"}, 
  {id: "b2-1", name: "Item 2-1", parentId: "b2"}, 
  {id: "b2-2", name: "Item 2-2", parentId: "b2"}, 
  {id: "b3", name: "Item 3", parentId: "b"}, 
  {id: "c1", name: "Item 1", parentId: "c"}, 
  {id: "c2", name: "Item 2", parentId: "c"}
]

console .log (forest (
  flat,
  ({id, parentId, ...rest}, f) => ({id, ...rest, children: f (id)}),
  (id, {parentId}) => parentId == id,
  null
))

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

<script>const forest = (xs, build, isChild, root) => xs .filter (x => isChild (root, x)).map (node => build (node, root => forest (xs, build, isChild, root)))</script>

Or the example Thankyou supplied might look like this:

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 newcomers here", forumLocked: false, forumDisplay: true }, 
  { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }
]

console .log (forest (
  input,
  (node, f) => ({...node, subforum: f(node .forumId)}),
  (id, {parentId}) => parentId == id,
  null
))

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

<script>const forest = (xs, build, isChild, root) => xs .filter (x => isChild (root, x)).map (node => build (node, root => forest (xs, build, isChild, root)))</script>

Significantly different input structures

These input structures all are similar in that each node points to an identifier for its parent, except of course the root nodes. But this technique would work just as well with one where parents point to a list of identifiers for their children. It takes a bit more work to create the root element (and here a helper function as well) but the same system will allow us to hydrate such a model:

const xs = [
  {content: 'abc', wordpress_id: 196, child_ids: []},
  {content: 'def', wordpress_id: 193, child_ids: [196, 199]},
  {content: 'ghi', wordpress_id: 199, child_ids: []},
  {content: 'jkl', wordpress_id: 207, child_ids: [208, 224]},
  {content: 'mno', wordpress_id: 208, child_ids: [209]},
  {content: 'pqr', wordpress_id: 209, child_ids: []},
  {content: 'stu', wordpress_id: 224, child_ids: []}
]

const diff = (xs, ys) => xs .filter (x => !ys.includes(x))

console .log (forest (
  xs,
  (node, fn) => ({...node, children: fn(node)}),
  ({child_ids}, {wordpress_id}) => child_ids .includes (wordpress_id),
  {child_ids: diff (xs .map (x => x .wordpress_id), xs .flatMap (x => x .child_ids))}
))

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

<script>const forest = (xs, build, isChild, root) => xs .filter (x => isChild (root, x)).map (node => build (node, root => forest (xs, build, isChild, root)))</script>

Here we have a different style of isChild, testing whether the potential child's id is in the list of ids supplied by the parent. And to create the initial root we have to scan the list of ids for those that do not appear as child ids. We use a diff helper to do this.

This different style is what I referred to above when discussing additional flexibility.

Only a first pass

I called this a "first pass" at such a solution because there's something I'm not really happy with here. We can use this technique to deal with removing now-unnecessary parent ids, and also to only include a children node if there are, in fact, actual children to include. For the orginal example, it might look like this:

console .log (forest (
  edges,
  ( {node: {wordpress_id, wordpress_parent, ...rest}}, 
    f, 
    kids = f (wordpress_id)
  ) => ({node: {
    ...rest,
    wordpress_id,
    ...(kids.length ? {children: kids} : {})
  }}),
  (id, {node: {wordpress_parent}}) => wordpress_parent == id,
  0
))

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

<script>const forest = (xs, build, isChild, root) => xs .filter (x => isChild (root, x)).map (node => build (node, root => forest (xs, build, isChild, root)))
        const edges = [{node: {content: 'abc', wordpress_id: 196, wordpress_parent: 193}}, {node: {content: 'def', wordpress_id: 193, wordpress_parent: 0}}, {node: {content: 'ghi', wordpress_id: 199, wordpress_parent: 193}}, {node: {content: 'jkl', wordpress_id: 207, wordpress_parent: 0}}, {node: {content: 'mno', wordpress_id: 208, wordpress_parent: 207}}, {node: {content: 'pqr', wordpress_id: 209, wordpress_parent: 208}}, {node: {content: 'stu', wordpress_id: 224, wordpress_parent: 207}}]</script>

Note that the results now only include children if there's something there. And the wordpress_parent node, now redundant, has been removed.

So this is possible to achieve with this technique, and we could do similar things for the other examples. But it comes at a fairly high complexity in the build function. I'm hoping that further reflection can yield a way to simplify those two features. So it's still a work in progress.

Conclusions

This sort of generalization, saving such reusable functions/modules as part of a personal toolkit, can vastly improve our codebases. We have just used the same function above for a number of obviously related, but subtly different behaviors. That can be nothing but a win.

This is not completed code, but it's usable like this, and there are several avenues of improvement to pursue.

A huge shout-out to Thankyou for the inspiration. I probably should have done this a while ago, but somehow this time it got through to me. Thanks!

Answer 2

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 another answer. @ScottSauyet, thank you for the concrete input example -

// Main.js
import { tree } from './Tree'   // <- use modules!

const input =
  [ { node: { content: 'abc', wordpress_id: 196, wordpress_parent: 193 } }
  , { node: { content: 'def', wordpress_id: 193, wordpress_parent: null } } // <- !
  , { node: { content: 'ghi', wordpress_id: 199, wordpress_parent: 193 } }
  , { node: { content: 'jkl', wordpress_id: 207, wordpress_parent: null } } // <- !
  , { node: { content: 'mno', wordpress_id: 208, wordpress_parent: 207 } }
  , { node: { content: 'pqr', wordpress_id: 209, wordpress_parent: 208 } }
  , { node: { content: 'stu', wordpress_id: 224, wordpress_parent: 207 } }
  ]

const result =
  tree                                     // <- make a tree
    ( input                                // <- array of nodes
    , ({ node }) => node.wordpress_parent  // <- foreign key
    , ({ node }, child) =>                 // <- node reconstructor function
        ({ node: { ...node, child: child(node.wordpress_id) } }) // <- primary key
    )

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

Output -

[
  {
    "node": {
      "content": "def",
      "wordpress_id": 193,
      "wordpress_parent": null,
      "child": [
        {
          "node": {
            "content": "abc",
            "wordpress_id": 196,
            "wordpress_parent": 193,
            "child": []
          }
        },
        {
          "node": {
            "content": "ghi",
            "wordpress_id": 199,
            "wordpress_parent": 193,
            "child": []
          }
        }
      ]
    }
  },
  {
    "node": {
      "content": "jkl",
      "wordpress_id": 207,
      "wordpress_parent": null,
      "child": [
        {
          "node": {
            "content": "mno",
            "wordpress_id": 208,
            "wordpress_parent": 207,
            "child": [
              {
                "node": {
                  "content": "pqr",
                  "wordpress_id": 209,
                  "wordpress_parent": 208,
                  "child": []
                }
              }
            ]
          }
        },
        {
          "node": {
            "content": "stu",
            "wordpress_id": 224,
            "wordpress_parent": 207,
            "child": []
          }
        }
      ]
    }
  }
]

In the input, I used wordpress_parent = null to represent a root node. We can use 0 like in your original program, if it is required. tree accepts a fourth parameter, root, the node to select as the basis of the tree. The default is null but we can specify 0, like -

const input =
  [ { node: { content: 'abc', wordpress_id: 196, wordpress_parent: 193 } }
  , { node: { content: 'def', wordpress_id: 193, wordpress_parent: 0 } }   // <- !
  , { node: { content: 'ghi', wordpress_id: 199, wordpress_parent: 193 } }
  , { node: { content: 'jkl', wordpress_id: 207, wordpress_parent: 0 } }   // <- !
  , { node: { content: 'mno', wordpress_id: 208, wordpress_parent: 207 } }
  , { node: { content: 'pqr', wordpress_id: 209, wordpress_parent: 208 } }
  , { node: { content: 'stu', wordpress_id: 224, wordpress_parent: 207 } }
  ]

const result =
  tree
    ( input
    , ({ node }) => node.wordpress_parent
    , ({ node }, child) =>
        ({ node: { ...node, child: child(node.wordpress_id) } })
    , 0                                                                    // <- !
    )

console.log(JSON.stringify(result, null, 2))
// same output ...

---

To make this post complete, I will include a copy of the Tree module -

// 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 node shape
  const one = (single) =>
    maker(single, next => many(cache.get(next)))

  return many(cache.get(root))
}

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

And the Index module dependency -

// 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 value shape
      , empty()
      )

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

For additional insight, I encourage you to read the original Q&A.