0

I have a source array as below :

 var source = [
     {
        node : 1, 
        text : "pen",
        parent : null 
     },
     {
        node : 11, 
        text : "pencil",
        parent : 1
     },
     {
         node : 12, 
         text : "mango",
         parent : 1
     },
     {
          node : 111, 
          text : "mango",
          parent : 11
     },
     {
            node : 112, 
           text : "banana",
           parent : 11
     },
      {
            node : 211, 
            text : "Cilli",
            parent : 12
     },
     {
           node : 1111, 
           text : "banana",
           parent : 111
      },
     {
           node : 2, 
           text : "Grapes",
           parent : null
     },
     {
          node : 21, 
           text : "Mango",
          parent : 2
    },
    {
         node : 3, 
        text : "banana",
        parent : null
    },

   ]

So as you see the parent of node 1 is null, hence it is the parent node. Also, the parent of node 11 is 1, hence 11 is children of node 1 and so on. I want a target array created like below : I need to use below array to create a tree

     var target = [

{
  node : 1 ,
  children :[
    {
      node : 11,
      children : [
          {
              node : 111,
                children :[
                      {
                              node:1111,
                             children :[]
                     }]
         },
        {
          node : 112,
          children:[]
        }

      ]
    },
     {
      node : 12,
      children : []
    },

  ]
},
{
  node : 2,
  children :[
  {
    node : 21,
    children :[]
  }]
},
{
  node:3,
  children:[]
}


]

I am trying array.forEach but that is not helping much

debugmode
  • 886
  • 7
  • 11
  • I’ll look at it again if I have a chance, but you should look at array.reduce. That is the way to go with things like this – dgo Nov 21 '21 at 02:59

2 Answers2

1
// using an object `childrenFor` to keep track of all `.children` arrays while we fill them.
const target = source.reduce((childrenFor, item) => {
  // adding the children array to item
  item.children = childrenFor[item.node] ??= [];

  // adding the item to the children array for its parent
  (childrenFor[item.parent] ??= []).push(item);

  //passing the cache through to the next iteration
  return childrenFor;
}, {})[null]; // selecting the list for items with `parent: null`

field ??= [] does "get or create array".

var source = [{
    node: 1,
    text: "pen",
    parent: null
  },
  {
    node: 11,
    text: "pencil",
    parent: 1
  },
  {
    node: 12,
    text: "mango",
    parent: 1
  },
  {
    node: 111,
    text: "mango",
    parent: 11
  },
  {
    node: 112,
    text: "banana",
    parent: 11
  },
  {
    node: 211,
    text: "Cilli",
    parent: 12
  },
  {
    node: 1111,
    text: "banana",
    parent: 111
  },
  {
    node: 2,
    text: "Grapes",
    parent: null
  },
  {
    node: 21,
    text: "Mango",
    parent: 2
  },
  {
    node: 3,
    text: "banana",
    parent: null
  },
];

const target = source.reduce((childrenFor, item) => {
  item.children = childrenFor[item.node] ??= [];
  (childrenFor[item.parent] ??= []).push(item);
  
  return childrenFor;
}, {})[null];

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

Edit in response to Mulans answer

I write JS for quite a while and it took me a few minutes to wrap my head around these few lines of code and how the data flows.

In my Team, that alone would be a reason to disqualify some piece of code as too complex and therefore error-prone (my opinion). But I also think that this code is unnecessarily complex.

Here my version of the generic makeTree function with the very same interface and without any recursion or ping-pong calls between functions:

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);
}


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 source = [
  { node: 1, text: "pen", parent: null },
  { node: 11, text: "pencil", parent: 1 },
  { node: 12, text: "mango", parent: 1 },
  { node: 111, text: "mango", parent: 11 },
  { node: 112, text: "banana", parent: 11 },
  { node: 211, text: "Cilli", parent: 12 },
  { node: 1111, text: "banana", parent: 111 },
  { node: 2, text: "Grapes", parent: null },
  { node: 21, text: "Mango", parent: 2 },
  { node: 3, text: "banana", parent: null },
];

const target = makeTree(
  source,
  item => item.parent,
  (item, getChildrenFor) => ({
    ...item,
    children: getChildrenFor(item.node)
  })
);

console.log(target);
.as-console-wrapper{top:0;max-height:100%!important}
Thomas
  • 9,760
  • 1
  • 12
  • 22
0

We can write makeTree as a generic function with 3 parameters -

  1. input as a flat list of nodes
  2. a function that identifies each node's parent
  3. a function that builds the tree nodes in your desired shape
const source =
  [{node:1,text:"pen",parent:null },{node:11,text:"pencil",parent:1},{node:12,text:"mango",parent:1},{node:111,text:"mango",parent:11},{node:112,text:"banana",parent:11},{node:211,text:"Cilli",parent:12},{node:1111,text:"banana",parent:111},{node:2,text:"Grapes",parent:null},{node:21,text:"Mango",parent:2},{node:3,text:"banana",parent:null},]

const result =
  makeTree
    ( source                                                   // 1
    , (node) => node.parent                                    // 2
    , (node, next) => ({ ...node, children: next(node.node) }) // 3
    )

makeTree is suitably generic allowing it to work on any array of inputs. And we have a terrific opportunity to learn about mutual recursion -

  1. many takes many inputs and calls one for each
  2. one builds a new node and calls many for all children

This circular arrangement turns out to be a perfect fit for branching recursive structures like the tree in your desired output -

function makeTree(input, indexer, maker, root = null) {
  const index = makeIndex(input, indexer)
  const many = (all = []) => all.map(one)                             // 1
  const one = (single = {}) => maker(single, r => many(index.get(r))) // 2
  return many(index.get(root))
}

makeTree is super fast even for large inputs thanks to its use of another generic, makeIndex, which uses a Map for fast lookups -

function makeIndex(items, indexer) {
  const insert = (r, k, v) => r.set(k, (r.get(k) ?? []).concat([ v ]))
  return items.reduce((r, i) => insert(r, indexer(i), i), new Map)
}

We're done with the implementation. Let's see the result -

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

Expand the snippet below to verify the result in your own browser -

function makeTree(input, indexer, maker, root = null) {
  const index = makeIndex(input, indexer)
  const many = (all = []) => all.map(one)
  const one = (single = {}) => maker(single, r => many(index.get(r)))
  return many(index.get(root))
}

function makeIndex(items, indexer) {
  const insert = (r, k, v) => r.set(k, (r.get(k) ?? []).concat([ v ]))
  return items.reduce((r, i) => insert(r, indexer(i), i), new Map)
}

const source =
  [{node:1,text:"pen",parent:null },{node:11,text:"pencil",parent:1},{node:12,text:"mango",parent:1},{node:111,text:"mango",parent:11},{node:112,text:"banana",parent:11},{node:211,text:"Cilli",parent:12},{node:1111,text:"banana",parent:111},{node:2,text:"Grapes",parent:null},{node:21,text:"Mango",parent:2},{node:3,text:"banana",parent:null},]

const result =
  makeTree
    ( source
    , (node) => node.parent
    , (node, next) => ({ ...node, children: next(node.node) })
    )

console.log(JSON.stringify(result, null, 2))
[
  {
    "node": 1,
    "text": "pen",
    "parent": null,
    "children": [
      {
        "node": 11,
        "text": "pencil",
        "parent": 1,
        "children": [
          {
            "node": 111,
            "text": "mango",
            "parent": 11,
            "children": [
              {
                "node": 1111,
                "text": "banana",
                "parent": 111,
                "children": []
              }
            ]
          },
          {
            "node": 112,
            "text": "banana",
            "parent": 11,
            "children": []
          }
        ]
      },
      {
        "node": 12,
        "text": "mango",
        "parent": 1,
        "children": [
          {
            "node": 211,
            "text": "Cilli",
            "parent": 12,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "node": 2,
    "text": "Grapes",
    "parent": null,
    "children": [
      {
        "node": 21,
        "text": "Mango",
        "parent": 2,
        "children": []
      }
    ]
  },
  {
    "node": 3,
    "text": "banana",
    "parent": null,
    "children": []
  }
]

See this related Q&A for advice on how to absract makeTree and makeIndex into their own modules. The techniques explained here will help you understand the basics for how and why we design programs in this way. If you have any questions, please ask.

Mulan
  • 119,326
  • 28
  • 214
  • 246
  • This is quite a bit to chew. I've updated [my answer](https://stackoverflow.com/a/70051634/6567275) in response to this. I find this unnecessarily complex but I'll take a closer look into mutual recursion. – Thomas Nov 24 '21 at 23:53
  • happy to inspire you to adapt the answer. if you are only experienced with imperative style, it makes sense that you would struggle with functional style. despite your initial observation, in functional style certain techniques and disciplines are used to make programs more robust and remove possibility of errors. if you see the [linked Q&A](https://stackoverflow.com/a/62138087/633183) i demonstrate how and why you would choose a modular approach for this, how it promotes greater code reuse and easier testing. – Mulan Nov 25 '21 at 00:58
  • on the other hand, your revision bundles all of this into a single-purpose function where indexing or "caching" is not generic and granular testing is harder to apply, and harder to ensure it's doing what you imagine/intend - a different kind of complexity when seen from another perspective. if you would like to learn more about mutual recursion, i have [other posts](https://stackoverflow.com/search?tab=active&q=user%3a633183%20%22mutual%20recursion%22) on the topic. – Mulan Nov 25 '21 at 01:00