How does one convert a tree like nested data structure of arrays and objects into a list of items with computed/counted id's and tracked parent id's?

user_12450991 0
Viewed 744

An API returns a nested data structure of arrays and objects. The data comes as a list of tree like objects, each with a possible parent-child relationship. The structure itself is shown by the following example code.

[{
  label: "search me",
  value: "searchme",
  children: [{

    label: "search me too",
    value: "searchmetoo",
    children: [{

      label: "No one can get me",
      value: "anonymous",
    }],
  }],
}, {
  label: "search me2",
  value: "searchme2",
  children: [{

    label: "search me too2",
    value: "searchmetoo2",
    children: [{

      label: "No one can get me2",
      value: "anonymous2",
    }],
  }],
}]

The above data has to be converted into a (flat) array of objects where each object will represent a former node element but with a unique primary key (id). Also a node's parent-id equals its parent's id (the primary key) except for root nodes that do not have a parent, and therefore the parent-id then should be null.

The target structure of the above provided source data then matches the following code ...

[{
  id: 1,                // DIAGID
  parentId: null,       // PARENTID
  label: "search me",   // DIAGNOSIS
  value: "searchme"     // DIAGTYPE
}, {
  id: 2,
  parentId: 1,
  label: "search me too",
  value: "searchmetoo"
}, {
  id: 3,
  parentId: 2,
  label: "No one can get me",
  value: "anonymous"
}, {
  id: 4,
  parentId: null,
  label: "search me2",
  value: "searchme2"
}, {
  id: 5,
  parentId: 4,
  label: "search me too2",
  value: "searchmetoo2"
}, {
  id: 6,
  parentId: 5,
  label: "No one can get me2",
  value: "anonymous2"
}]
mapping recursion data-structures arrays javascript
5 Answers

You could take a recursive method for Array#flatMap and store parent for the next call.

This approach increments id for all nodes.

const
    flatTree = (id => parent => ({ children = [], ...object }) => [
        { id: ++id, ...object, parent },
        ...children.flatMap(flatTree(id))
    ])(0),
    tree = [{ label: 'search me', value: 'searchme', children: [{ label: 'search me too', value: 'searchmetoo', children: [{ label: 'No one can get me', value: 'anonymous' }] }] }, { label: 'four', searchme: '4four' }],
    flat = tree.flatMap(flatTree(null));

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

user_14476750

Here is a recursive function dfs that performs a pre-order traversal through the input tree, and passes along a counter that feeds the id property that will be used in the output. Also the current node's id is passed as parentId to the recursive call:

const dfs = (children, counter={id: 1}, parentId=null) =>
    children.flatMap(({children=[], ...node}) => [{ 
        ...counter, 
        parentId,
        ...node
    }].concat(dfs(children, counter, counter.id++)));

const response = [{label: "search me",value: "searchme",children: [{label: "search me too",value: "searchmetoo",children: [{label: "No one can get me",value: "anonymous",}],}],}, {label: "search me2",value: "searchme2",children: [{label: "search me too2",value: "searchmetoo2",children: [{label: "No one can get me2",value: "anonymous2",}],}],}];
const result = dfs(response);
console.log(result);

user_54598390

I was going to say a recursive tree walk is all you need, but you can accomplish the same thing easily with a generator:

function *visitNodes( root, parent = null, id = 0 ) {
  
  const node = {
    ...root,
    id : ++id,
    parentId = parent ? parent.id : null
  };
  delete node.children;
  
  yield node;
  
  for ( const child of root.children ?? [] ) {
    yield *visitNodes(child, node, id);
  }
  
}

Having defined the generator, you can either iterate over the nodes:

for (const node of visitNodes( tree ) ) {
  // do something useful with node here
}

You can convert it into a list easily, either with the spread operator:

const nodes  = [...visitNodes(tree)];

or by using Array.from():

const nodes = Array.from( visitNodes(tree) );
user_4674730

A single recursively implemented reduceer functionality which maps and collects any item generically does the job.

It utilizes a collector object as the reduce method's 2nd argument (and the reducer's initial value). The collector's result array collects any item. And count gets incremented constantly and assigned as a collected item's id (former DIAGID) whereas an item's parentId (former PARENTID) gets updated as needed in order to always reflect the current recursive call stack ...

function countMapAndCollectNestedItemRecursively(collector, item) {

  let { count = 0, parentId = null, result } = collector;
  const { children = [], ...itemRest } = item;

  result.push({

    id: ++count,
    parentId,

    ...itemRest,
  });
  count = children.reduce(

    countMapAndCollectNestedItemRecursively,
    { count, parentId: count, result }

  ).count;

  return { count, parentId, result };
}

const sampleData = [{
  label: "FOO",
  value: "foo",
  children: [{

    label: "FOO BAR",
    value: "fooBar",
    children: [{

      label: "FOO BAR BAZ",
      value: "fooBarBaz",
    }],
  }, {
    label: "FOO BIZ",
    value: "fooBiz",
    children: [{

      label: "FOO BIZ BUZ",
      value: "fooBizBuz",
    }],
  }],
}, {
  label: "BAR",
  value: "bar",
  children: [{

    label: "BAR BAZ",
    value: "barBaz",
    children: [{

      label: "BAR BAZ BIZ",
      value: "barBazBiz",
      children: [{

        label: "BAR BAZ BIZ BUZ",
        value: "barBazBizBuz",
      }],
    }, {
      label: "BAR BAZ BUZ",
      value: "barBazBuz",
    }],
  }, {
    label: "BAR BIZ",
    value: "barBiz",
    children: [{

      label: "BAR BIZ BUZ",
      value: "barBizBuz",
    }],
  }],
}];

console.log(
  sampleData.reduce(

    countMapAndCollectNestedItemRecursively,
    { result: [] },

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

user_26272430

This version is something of a mash-up of ideas from trincot and Nicholas Carey. From trincot's answer (which actually answers a different, but closely related question) I steal his {ctr: id: 1} handling. And from Nicholas, I use the generator to iterate through the values more easily, although I simplify a bit from there.

I think they combine to give a nice solution:

const flatten = function * (xs, ctr = {id: 1}, parent = null) {
  for (let {children = [], ...x} of xs) {
    const node = {id: ctr .id ++, parentId: parent ? parent .id : null, ...x}
    yield node
    yield * flatten (children, ctr, node)
  }
}

const transform = (xs) => [...flatten (xs)]

const response = [{label: "search me", value: "searchme", children: [{label: "search me too", value: "searchmetoo", children: [{label: "No one can get me", value: "anonymous"}]}]}, {label: "search me2", value: "searchme2", children: [{label: "search me too2", value: "searchmetoo2", children: [{label: "No one can get me2", value: "anonymous2"}]}]}]

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

user_12436410
Related