How to iteratively nest objects within an object

Question

I have an array that looks like this:

const arr = [
{
  parent: 'A',
  children: ['B'],
},
{
  parent: 'B',
  children: ['C'],
},
{
  parent: 'C',
  children: ['D']
}];

and I want to create a function that will take this array and result in the following object:

const result = {
  parent: 'A',
  children: [{
    parent: 'B',
    children: [{
      parent: 'C',
      children: [{
        parent: 'D',
        children: []
      }]
    }]
  }]
};

so the result type would look like:

type Result = {
  parent: string;
  children: Result[];
};

What I've tried so far:

type TInput = {
  parent: string;
  children: string[];
};

type Result = {
  parent: string;
  children: Result[];
};

// can assume we know initial parent is 'A'
const fn = (parent: string, inputArr: TInput[]) => {
  const result: TResult[] = [];

  let newParent: string[] = [];
  while (newParent.length !== 0) {
    const index = inputArr.findIndex(
      (input) => input.parent === parent
    );
    result.push({
      parent: inputArr[index].parent,
      children: [], // need to populate on next pass?
    });
    newParent = inputArr[index].children;
  }
  return result;
};

I don't know how many objects will be in the input array, but can assume first object is known to be initial parent/child ('A' in the example). Any help much appreciated. Thanks

What is this condition supposed to do? `while (newParent.length !== 0)` `newParent` is always an empty array at first — Konrad, Nov 14 '22 at 22:47
Does this answer your question? [Build tree array from flat array in javascript](https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript) — pilchard, Nov 14 '22 at 22:56
Also your result tree property naming conflicts with the flat data. `parent: 'A'` should indicate that the node is a child of `A` but in your tree the node with `parent: 'B'` is actually a child of `A` — pilchard, Nov 14 '22 at 23:12
This smells like a single loop, with `reduce` inside. But if it is a one-root tree, then no loop will be needed at all, just a single `reduce`. — vitaly-t, Nov 14 '22 at 23:24
@PeterSeliger I totally agree, which is what I was pointing to in my initial comment. It is solvable, but requires an extra loop to determine root nodes (nodes that are not children of any other node). — pilchard, Nov 15 '22 at 00:01
In my opinion the chosen source structure already has flaws. It is not bijective/biunique in terms of the parent-child and each child-parent relationship. It gets obvious when one tries to read and figure out the purpose of the transformed target structure. Both structures are far from being intuitive. The source structure rather should be ... `const arr = [{ id: 'A', parentId: null }, { id: 'B', parentId: 'A' }, { id: 'C', parentId: 'B' }];` ... the expected result then would be ... `{ id: 'A', parentId: null, children: [{ id: 'B', parentId: 'A', children: [{ id: 'C', parentId: 'B' }] }] }`. — Peter Seliger, Nov 15 '22 at 00:08
@PeterSeliger I get your point but is it not relative? How is `{ id: 'B', parentId: 'A' }` more correct than `{ id: 'B', childId: 'C' }`? The first pass for me I can only discern children for a relative node, so to flip the direction requires extra computation — Iain McHugh, Nov 25 '22 at 11:50
@IainMcHugh ... 1/3 ... With the originally provided structure one has several disadvantages ... it is not expressive because an object features an own id which is not named `id` but `parent` which is totally confusing because the latter sounds like the reference to this very object's parent but not the object's own `id`. An object then features already the `children` array which contains placeholder string values, the `parent` value of some source objects which already again is counter intuitive, even more since there are placeholder ids to objects which do not even exist like ... — Peter Seliger, Nov 25 '22 at 12:26
@IainMcHugh ... 2/3 ... `{ parent: 'C', children: ['D'], }`. The `'D'` is just a hint to an object which has to be created in case it could not be found within the source-structure. The entire source-structure feels inside-out whereas an array of expressive objects like `[{ id: 'A', parentId: null }, { id: 'B', parentId: 'A' }, { id: 'C', parentId: 'B' }]` is very explicit about what each item is and where it belongs to. — Peter Seliger, Nov 25 '22 at 12:27
@IainMcHugh ... 3/3 ... Another advantage is, that all these objects already exist. They don't need to be created like the OP's `D`-item, they just need to be augmented by a `children` array in case of existing children. — Peter Seliger, Nov 25 '22 at 12:27
@IainMcHugh ... of cause the changed naming schema of the OP's above comment already helps ... but it then has to be not `{ id: 'B', childId: 'C' }` but `{ id: 'B', childIds: ['C'] }` since an object can have more than just one child. — Peter Seliger, Nov 25 '22 at 12:37

Kameneth · Accepted Answer · 2022-11-15T01:48:08.577

I'd use a parent map to recreate children attribute as arrays of parent objects:

const arr = [
    {
      parent: 'A',
      children: ['B'],
    },
    {
      parent: 'B',
      children: ['C'],
    },
    {
      parent: 'C',
      children: ['D']
    },
    {
      parent: 'D',
      children: []
    }
  ];

const makeTree = (manyParents,rootName) => {
    // copy parent objects into a map.
    let mapIt = new Map(manyParents.map(pObject => {
      return [pObject.parent, pObject];
    }));
    
    // recreate children arrays for each parents.
    mapIt.forEach((oneParent) => {
        let newChildrenArray = [];
        //find every children objects.
        oneParent.children.forEach((oneChild) => {
            newChildrenArray.push(mapIt.get(oneChild));
        });
        //replace children array.
        oneParent.children = newChildrenArray;
    });
    return mapIt.get(rootName);
}

let tree = makeTree(arr,'A');
console.log(tree)

score 0 · Answer 2 · answered Nov 15 '22 at 16:06

You can use Array#reverse and Array#reduce methods as follows:

const 
    arr = [ { parent: 'A', children: ['B'], }, { parent: 'B', children: ['C'], }, { parent: 'C', children: ['D'] }],

    output = arr.reverse().reduce(
      (acc,{parent,children}) =>
      !acc.parent ? 
      ({parent,children:children.map( ([parent]) => ({parent,children:[]}) )}):
      ({parent,children:[acc]}),{}
    );
    
console.log( output );

score -2 · Answer 3 · answered Nov 15 '22 at 00:05

This seems to do the job :

This is the ts version :

// here i just copy your data
const data = [{
    parent: 'A',
    children: ['B'],
  },
  {
    parent: 'C',
    children: ['D']
  },
  {
    parent: 'B',
    children: ['C'],
  }
];

const expectedResult = {
  parent: 'A',
  children: [{
    parent: 'B',
    children: [{
      parent: 'C',
      children: [{
        parent: 'D',
        children: []
      }]
    }]
  }]
};

type TInput = {
  parent: string;
  children: string[];
};

type TResult = {
  parent: string;
  children: TResult[];
};


// there is the function that takes an input (the parent element) and an array (all the children)
const parseArray = (obj: TInput, arr: TInput[]): TResult => {
  return {
    parent: obj.parent,
    // if the children exists on the array, we use it, else we create an empty one, which will be used to recusivly generate the tree
    children: obj.children.map(child => data.find(e => e.parent === child) ?? {
      parent: child,
      children: []
    }).map(e => parseArray(e, arr))
  }
}

// we get the root obj (as you said the first el)
const root = data.shift()!

// and we call the function
console.log(parseArray(root, data))

// we verify that the objects are the same using json (directly using == on objects compares their locations on the disk)
console.log(JSON.stringify(parseArray(root, data)) === JSON.stringify(expectedResult))

And this is the snipped (we can't run ts directly on snippets) :

// here i just copy your data
const data = [{
    parent: 'A',
    children: ['B'],
  },
  {
    parent: 'C',
    children: ['D']
  },
  {
    parent: 'B',
    children: ['C'],
  }
];

const expectedResult = {
  parent: 'A',
  children: [{
    parent: 'B',
    children: [{
      parent: 'C',
      children: [{
        parent: 'D',
        children: []
      }]
    }]
  }]
};

// there is the function that takes an input (the parent element) and an array (all the children)
const parseArray = (obj, arr) => {
  return {
    parent: obj.parent,
    // if the children exists on the array, we use it, else we create an empty one, which will be used to recusivly generate the tree
    children: obj.children.map(child => data.find(e => e.parent === child) ?? {
      parent: child,
      children: []
    }).map(e => parseArray(e, arr))
  }
}

// we get the root obj (as you said the first el)
const root = data.shift()

// and we call the function
console.log(parseArray(root, data))

// we verify that the objects are the same using json (directly using == on objects compares their locations on the disk)
console.log(JSON.stringify(parseArray(root, data)) === JSON.stringify(expectedResult))

How to iteratively nest objects within an object

3 Answers3