Build tree array from flat array in Typescript / JavaScript

Question

I have a complex json file that I have to handle with TypeScript / Javascript to make it hierarchical, in order to later build a questionnaire. Every entry of the json has a Id (unique), ParentId (0 If root), Text, Description.

My Typescript Interface

export interface Question {
    Id: number;
    Text: string;
    Desc: string;
    ParentId: number;
    ChildAnswers?: Answer[];
}

export interface Answer {
    Id: number;
    Text: string;
    Desc: string;
    ParentId: number;
    ChildQuestion?: Question;
}

I can guarantee that when the object is an answer it will only have one child which we can assume to be a question.

Flat Data Example :

[
{
    Id: 1,
    Text: 'What kind of apple is it?',
    Desc: '',
    ParentId: 0
},
{
    Id: 2,
    Text: 'Green Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 3,
    Text: 'Red Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 4,
    Text: 'Purple GMO Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 5,
    Text: 'What is the issue with the apple?',
    Desc: '',
    ParentId: 2
},
{
    Id: 6,
    Text: 'Spoiled.',
    Desc: '',
    ParentId: 5
},
{
    Id: 7,
    Text: 'Taste Bad.',
    Desc: '',
    ParentId: 5
},
{
    Id: 8,
    Text: 'Too Ripe.',
    Desc: '',
    ParentId: 5
},
{
    Id: 9,
    Text: 'Is not an apple.',
    Desc: '',
    ParentId: 5
},
{
    Id: 10,
    Text: 'The apple was not green.',
    Desc: '',
    ParentId: 5
},
... So on ...
]

My Goal

{
    Id: 1,
    Text: 'What kind of apple is it?',
    Desc: '',
    ParentId: 0,
    ChildAnswers: [
        {
            Id: 2,
            Text: 'Green Apple',
            Desc: '',
            ParentId: 1,
            ChildQuestion: {
                Id: 5,
                Text: 'What is the issue with the apple?',
                Desc: '',
                ParentId: 2,
                ChildAnswers: [
                    {
                        Id: 6,
                        Text: 'Spoiled.',
                        Desc: '',
                        ParentId: 5,
                        ... So on ...
                    },
                    {
                        Id: 7,
                        Text: 'Taste Bad.',
                        Desc: '',
                        ParentId: 5,
                        ... So on ...
                    },
                    {
                        Id: 8,
                        Text: 'Too Ripe.',
                        Desc: '',
                        ParentId: 5,
                        ... So on ...
                    },
                    {
                        Id: 9,
                        Text: 'Is not an apple.',
                        Desc: '',
                        ParentId: 5,
                        ... So on ...
                    },
                    {
                        Id: 10,
                        Text: 'The apple was not green.',
                        Desc: '',
                        ParentId: 5,
                        ... So on ...
                    },
                    ... So on ...
                ]
            }
        },
        {
            Id: 3,
            Text: 'Red Apple',
            Desc: '',
            ParentId: 1,
            ... So on ...
        },
        {
            Id: 4,
            Text: 'Red Apple',
            Desc: '',
            ParentId: 1,
            ... So on ...
        }
        ... So on ...
    ]
}

I'm currently using this list_to_tree function I found here on stackoverflow, I just don't know if how to tell a question and answer apart. Should I just check to see if the length is one for a question or at odd intervals mark it?:

function list_to_tree(list) {
    var map = {}, node, roots = [], i;
    for (i = 0; i < list.length; i += 1) {
        map[list[i].Id] = i; // initialize the map
        list[i].Children = []; // initialize the children
    }
    for (i = 0; i < list.length; i += 1) {
        node = list[i];
        if (node.ParentId !== 0) {
            // if you have dangling branches check that map[node.ParentId] exists
            list[map[node.ParentId]].Children.push(node);
        } else {
            roots.push(node);
        }
    }
    return roots;
}

Are you trying to do this in place, or is it acceptable if a new array is constructed? — nephiw
– nephiw, Commented Nov 21, 2019 at 16:33
Also, is the data sorted the way you have presented it or could it be in any order? — nephiw
– nephiw, Commented Nov 21, 2019 at 16:39
A new array can be constructed and the data could be sorted if it makes it easier. — Matt
– Matt, Commented Nov 21, 2019 at 16:40
It looks like the crux of this is how do you identify which is a question and which is an answer. I assume you must accept that it alternates question/answer or is there a better way? — nephiw
– nephiw, Commented Nov 21, 2019 at 16:48
Yes, they alternate and basically have a guaranteed data structure of question answers repeating. — Matt
– Matt, Commented Nov 21, 2019 at 16:56

nephiw · Accepted Answer · 2019-11-21 18:09:14Z

Here is a brute force solution to the problem:

var flat = [
{
    Id: 1,
    Text: 'What kind of apple is it?',
    Desc: '',
    ParentId: 0
},
{
    Id: 2,
    Text: 'Green Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 3,
    Text: 'Red Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 4,
    Text: 'Purple GMO Apple',
    Desc: '',
    ParentId: 1
},
{
    Id: 5,
    Text: 'What is the issue with the apple?',
    Desc: '',
    ParentId: 2
},
{
    Id: 6,
    Text: 'Spoiled.',
    Desc: '',
    ParentId: 5
},
{
    Id: 7,
    Text: 'Taste Bad.',
    Desc: '',
    ParentId: 5
},
{
    Id: 8,
    Text: 'Too Ripe.',
    Desc: '',
    ParentId: 5
},
{
    Id: 9,
    Text: 'Is not an apple.',
    Desc: '',
    ParentId: 5
},
{
    Id: 10,
    Text: 'The apple was not green.',
    Desc: '',
    ParentId: 5
},
]

// first get the roots
const tree = flat.filter((question) => question.ParentId === 0);

// Next we are going to call alternating methods recursively.
function populateQuestionChildren(node) {
  const { Id } = node;
  flat.forEach((answer) => {
    if (answer.ParentId === Id) {
      if (!node.ChildAnswers) {
        node.ChildAnswers = [];
      }
      node.ChildAnswers.push(answer);
      populateAnswerChildren(answer);
    }
  });
}

function populateAnswerChildren(node) {
  const { Id } = node;
  flat.forEach((question) => {
    if (question.ParentId === Id) {
      if (!node.ChildQuestions) {
        node.ChildQuestions = [];
      }
      node.ChildQuestions.push(question);
      populateQuestionChildren(question);
    }
  });
}

// Kick off the build for each question tree. 
tree.forEach((question) => {
  populateQuestionChildren(question);
});

It is likely that there are more elegant solutions - but given that this will be only few dozen or a few hundred question/answers - this should get you what you need.

[EDIT]

I used your interfaces and discovered a problem with my code. There is only one "ChildQuestion" on an Answer object. So here is my change to TypeScript to make it work properly. I hope it helps:


interface Question {
  Id: number;
  Text: string;
  Desc: string;
  ParentId: number;
  ChildAnswers ? : Answer[];
}

interface Answer {
  Id: number;
  Text: string;
  Desc: string;
  ParentId: number;
  ChildQuestion ? : Question;
}

// first get the roots
const tree = flat.filter((question) => question.ParentId === 0);

function populateQuestionChildren(node: Question) {
  const { Id } = node;
  flat.forEach((answer) => {
    if (answer.ParentId === Id) {
      if (!node.ChildAnswers) {
        node.ChildAnswers = [];
      }
      node.ChildAnswers.push(answer);
      populateAnswerChild(answer);
    }
  });
}

function populateAnswerChild(answer: Answer) {
  const { Id } = answer;
  // switch to every so we can break early once a question is found.
  flat.every((node) => {
    if (node.ParentId === Id) {
      answer.ChildQuestion = node;
      populateQuestionChildren(node);
      return false;
    }
    return true;
  });
}

tree.forEach((question) => {
  populateQuestionChildren(question);
});

You can copy/paste the entire thing into the console to see it execute. Hopefully, this will get you what you need.

junwen-k · Accepted Answer · 2019-11-21 17:27:07Z

I've created an answer based on @nephiw's answer. Since the key will always be Questions or Answers, odd number will always be Answers and even number will be Questions. You can simplify into one function instead of two.

const items = [
  {
    Id: 1,
    Text: "What kind of apple is it?",
    Desc: "",
    ParentId: 0
  },
  {
    Id: 2,
    Text: "Green Apple",
    Desc: "",
    ParentId: 1
  },
  {
    Id: 3,
    Text: "Red Apple",
    Desc: "",
    ParentId: 1
  },
  {
    Id: 4,
    Text: "Purple GMO Apple",
    Desc: "",
    ParentId: 1
  },
  {
    Id: 5,
    Text: "What is the issue with the apple?",
    Desc: "",
    ParentId: 2
  },
  {
    Id: 6,
    Text: "Spoiled.",
    Desc: "",
    ParentId: 5
  },
  {
    Id: 7,
    Text: "Taste Bad.",
    Desc: "",
    ParentId: 5
  },
  {
    Id: 8,
    Text: "Too Ripe.",
    Desc: "",
    ParentId: 5
  },
  {
    Id: 9,
    Text: "Is not an apple.",
    Desc: "",
    ParentId: 5
  },
  {
    Id: 10,
    Text: "The apple was not green.",
    Desc: "",
    ParentId: 5
  }
];

const root = items.filter(item => item.ParentId === 0);
const populateChildren = (curentItem, nested) => {
  const { Id } = curentItem;
  const key = nested % 2 === 1 ? 'ChildAnswers' : 'ChildQuestions';
  items.forEach((item) => {
    if (item.ParentId === Id) {
      if (!curentItem[key]) {
        curentItem[key] = [];
      }
      curentItem[key].push(item);
      populateChildren(item, nested + 1);
    }
  });
}
root.forEach((item) => { 
  populateChildren(item, 1);
});
console.log(root);

Nina Scholz · Accepted Answer · 2019-11-21 18:35:17Z

You could take an approach where you collect the parts independently of the order of the given data and build a tree and map the children by toggeling the question/answer scheme.

var data = [{ Id: 1, Text: 'What kind of apple is it?', Desc: '', ParentId: 0 }, { Id: 2, Text: 'Green Apple', Desc: '', ParentId: 1 }, { Id: 3, Text: 'Red Apple', Desc: '', ParentId: 1 }, { Id: 4, Text: 'Purple GMO Apple', Desc: '', ParentId: 1 }, { Id: 5, Text: 'What is the issue with the apple?', Desc: '', ParentId: 2 }, { Id: 6, Text: 'Spoiled.', Desc: '', ParentId: 5 }, { Id: 7, Text: 'Taste Bad.', Desc: '', ParentId: 5 }, { Id: 8, Text: 'Too Ripe.', Desc: '', ParentId: 5 }, { Id: 9, Text: 'Is not an apple.', Desc: '', ParentId: 5 }, { Id: 10, Text: 'The apple was not green.', Desc: '', ParentId: 5 }],
    tree = function (data, root) {
        const
            next = { ChildAnswers: 'ChildQuestion', ChildQuestion: 'ChildAnswers' },
            toggle = type => ({ children, ...o }) =>
                Object.assign(o, children && { [type]: children.map(toggle(next[type])) }),
            t = {};

        data.forEach(o => {
            Object.assign(t[o.Id] = t[o.Id] || {}, o);
            t[o.ParentId] = t[o.ParentId] || {};
            t[o.ParentId].children = t[o.ParentId].children || [];
            t[o.ParentId].children.push(t[o.Id]);
        });
        return t[root].children.map(toggle('ChildAnswers'));
    }(data, 0);

console.log(tree);

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

marandiiii · Accepted Answer · 2022-12-07 11:26:38Z

0

my code :

  makeTree(nodes: any[], parentId: any): any {
return nodes
  .filter((node) => node.parentId === parentId)
  .reduce(
    (tree, node) => [
      ...tree,
      {
        ...node,
        children: this.makeTree(nodes, node.id),
      },
    ],
    []
  ); }

Generate Node from Array

edited Dec 7, 2022 at 11:26

answered Dec 7, 2022 at 8:20

marandiiii

2110 bronze badges

1 Comment

camille Over a year ago

It would be better if you explained why this solves the problem

Collectives™ on Stack Overflow

Build tree array from flat array in Typescript / JavaScript

4 Answers 4

[EDIT]

1 Comment

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

[EDIT]

1 Comment

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related