CODEWITHSUNDEEP
javascripttree
Morpheu5
Morpheu5

Reputation: 2801

How do I flatten a (forest of) trees?

I have a forest of trees of arbitrary height, more or less like this:

let data = [
  { "id": 2, "name": "AAA", "parent_id": null, "short_name": "A" },
  {
    "id": 10, "name": "BBB", "parent_id": null, "short_name": "B", "children": [
      {
        "id": 3, "name": "CCC", "parent_id": 10, "short_name": "C", "children": [
          { "id": 6, "name": "DDD", "parent_id": 3, "short_name": "D" },
          { "id": 5, "name": "EEE", "parent_id": 3, "short_name": "E" }
        ]
      },
      {
        "id": 4, "name": "FFF", "parent_id": 10, "short_name": "F", "children": [
          { "id": 7, "name": "GGG", "parent_id": 4, "short_name": "G" },
          { "id": 8, "name": "HHH", "parent_id": 4, "short_name": "H" }
        ]
      }]
  }
];

And I'm trying to produce a representation of all the root-to-leaves paths, something like this

[
  [
    {
      "id": 2,
      "name": "AAA"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 3,
      "name": "C"
    },
    {
      "id": 6,
      "name": "DDD"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 3,
      "name": "C"
    },
    {
      "id": 5,
      "name": "EEE"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 4,
      "name": "F"
    },
    {
      "id": 7,
      "name": "GGG"
    }
  ],
  [
    {
      "id": 10,
      "name": "B"
    },
    {
      "id": 4,
      "name": "F"
    },
    {
      "id": 8,
      "name": "HHH"
    }
  ]
]

So I wrote the following code:

function flattenTree(node, path = []) {
    if (node.children) {
        return node.children.map(child => flattenTree(child, [...path, child]));
  } else {
    let prefix = path.slice(0, path.length - 1).map(n => ({ id: n.id, name: n.short_name }));
    let last = path[path.length - 1];
    return [...prefix, { id: last.id, name: last.name } ];
  }
}

let paths = data.map(n => flattenTree(n, [n]));

but paths comes out with extra nesting, like this:

[
  [
    {
      "id": 2,
      "name": "AAA"
    }
  ],
  [
    [
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 3,
          "name": "C"
        },
        {
          "id": 6,
          "name": "DDD"
        }
      ],
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 3,
          "name": "C"
        },
        {
          "id": 5,
          "name": "EEE"
        }
      ]
    ],
    [
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 4,
          "name": "F"
        },
        {
          "id": 7,
          "name": "GGG"
        }
      ],
      [
        {
          "id": 10,
          "name": "B"
        },
        {
          "id": 4,
          "name": "F"
        },
        {
          "id": 8,
          "name": "HHH"
        }
      ]
    ]
  ]
]

I lost count of the many ways in which I tried to fix this, but it does look like the algorithm should not produce the extra nesting -- or my eyes are just so crossed by now that I couldn't see my mistake if someone stuck their finger on it.

Can someone help? Feel free to peruse this JSFiddle https://jsfiddle.net/png7x9bh/66/

Upvotes: 1

Views: 112

Answers (1)

ibrahim mahrir
ibrahim mahrir

Reputation: 31692

The extra nestings are created by map. map just wraps the results into an array and returns them, it doesn't care if it is called on child nodes or not. Use reduce and just concat (or push, whatever suits your performance) the results into the first level array directly:

let data = [{"id":2,"name":"AAA","parent_id":null,"short_name":"A"},{"id":10,"name":"BBB","parent_id":null,"short_name":"B","children":[{"id":3,"name":"CCC","parent_id":10,"short_name":"C","children":[{"id":6,"name":"DDD","parent_id":3,"short_name":"D"},{"id":5,"name":"EEE","parent_id":3,"short_name":"E"}]},{"id":4,"name":"FFF","parent_id":10,"short_name":"F","children":[{"id":7,"name":"GGG","parent_id":4,"short_name":"G"},{"id":8,"name":"HHH","parent_id":4,"short_name":"H"}]}]}];

function flattenTree(node, path = []) {
    let pathCopy = Array.from(path);
    pathCopy.push({id: node.id, name: node.name});
    if(node.children) {
        return node.children.reduce((acc, child) => acc.concat(flattenTree(child, pathCopy)), []);
    }
    return [pathCopy];
}

let result = data.reduce((result, node) => result.concat(flattenTree(node)), []);
console.log(JSON.stringify(result, null, 3));

Upvotes: 2

Related Questions