Reverse nested tree with appending values to an array-CodePudding

I have the following data structure

[
    {
        "id": 3,
        "name" "Important Topic 3",
        "questions": [array of questions],
        "topics: [array of topics],
        "parentTopic": {
                "id": 2,
                "name": "Parent Topic 1",
                "parentTopic": {
                    "id": 1,
                    "name": "Parent Topic 2",
                    "parentTopic: null
                 }
            }
     },
    {
        "id": 4,
        "name" "Important Topic 4",
        "questions": [array of questions],
        "topics: [array of topics],
        "parentTopic": {
                "id": 2,
                "name": "Parent Topic 1",
                "parentTopic": {
                    "id": 1,
                    "name": "Parent Topic 2",
                    "parentTopic: null
                 }
            }
     }
]

I want to end up with the following

[
    {
        "id": 1,
        "name": "Parent Topic 2",
        "topics": [
            {
                "id": 2,
                "name": "Parent Topic 1"
                "topics": [
                    {
                      "id": 3,
                      "name: "Important Topic 3",
                      "questions": [array of questions],
                      "topics: [array of topics]
                    },
                    {
                      "id": 4,
                      "name: "Important Topic 4",
                      "questions": [array of questions],
                      "topics: [array of topics]
                    }
                ]
            }
        ]
    }
]

I have some code which I got also as help from the awesome stackoverflow community, but it only works if I have nested dictionary objects, not lists of dictionaries in an array. Here is the stackoverflow reference - Reverse Nested Tree in Javascript

I would really appreciate if you could help solve this puzzle :)

CodePudding user response：

You could collect nodes -- as you visit them -- in a map, keyed by their id, so you can know when you meet a node that you already have placed in the target structure. So visit the source nodes in depth-first order (pre-order) and build the new hierarchy bottom-up, but stopping when a node is encountered that is already in the target structure. At that point put the last created target node inside its topics array.

Here is an implementation of that idea:

function invertHierarchy(leaves) {
    const root = { id: null, topics: [] };
    const map = { null: root }; 
    for (let { id, parentTopic, ...rest } of leaves) {
        let node = map[id] = { id, ...rest }; // leaf
        while (true) {
            ({id, parentTopic, ...rest} = parentTopic ?? root);
            if (id in map) break;
            map[id] = node = { id, ...rest, topics: [node] };
        }
        map[id].topics.push(node);
    }
    return root.topics;
}

// Example run:
const leaves = [{"id": 3,"name": "Important Topic 3","questions": [],"topics": ["a"],"parentTopic": {"id": 2,"name": "Parent Topic 1","parentTopic": {"id": 1,"name": "Parent Topic 2","parentTopic": null}}},{"id": 4,"name": "Important Topic 4","questions": [],"topics": ["b"],"parentTopic": {"id": 2,"name": "Parent Topic 1","parentTopic": {"id": 1,"name": "Parent Topic 2","parentTopic": null}}}];
const result = invertHierarchy(leaves);
console.log(result);

CodePudding user response：

This seems to achieve what you want :

// The json data
const jsonData = `[
  {
      "id": 3,
      "name": "Important Topic 3",
      "questions": [],
      "topics": [],
      "parentTopic": {
              "id": 2,
              "name": "Parent Topic 1",
              "parentTopic": {
                  "id": 1,
                  "name": "Parent Topic 2",
                  "parentTopic": null
               }
          }
   },
  {
      "id": 4,
      "name": "Important Topic 4",
      "questions": [],
      "topics": [],
      "parentTopic": {
              "id": 2,
              "name": "Parent Topic 1",
              "parentTopic": {
                  "id": 1,
                  "name": "Parent Topic 2",
                  "parentTopic": null
               }
          }
   }
]`

const baseData = JSON.parse(jsonData)


// List of all topics (children and parents)
let topics = []

// Recursive function to add children elements
const listTopics = topic => {
  // Push only if it doesn't already exists to avoid duplicates
  if (!topics.some(e => e.id === topic.id))
    topics.push(topic)

  // The recursive part
  if (topic.parentTopic)
    listTopics(topic.parentTopic)
}

// Ignite
baseData.forEach(listTopics)


// Runs while none of the topics elements has a parent
// You can replace it by `topics.length > 1` if you only have one root topic
while (topics.some(e => e.parentTopic)) {
  const parent = topics.shift()

  topics = topics.filter(topic => {
    if (topic.parentTopic && topic.parentTopic.id === parent.id) {
      if (!parent.topics)
        parent.topics = []

      parent.topics.push(topic)
      return false
    }

    return true
  })

  topics.push(parent)
}

// Print the new tree as JSON with some modifications to avoid circulars between parents and children
console.log(JSON.stringify(topics, (key, value) => key === 'parentTopic' ? (value === null ? null : {
  id: value.id
}) : value, '  '))