How can I get all possible paths to traverse the tree?

How can I get all possible paths to traverse the tree?

Problem Description:

The question is: How can I get an array of all tree paths?

In this example there are 5 ways:

[
  [{ 1: "2" }, { 3: "4" }],
  [{ 1: "2" }, { 3: "5" }],
  [{ 1: "6" }, { 7: "8" }],
  [{ 1: "6" }, { 7: "9" }, { 10: "11" }],
  [{ 1: "6" }, { 7: "9" }, { 10: "12" }],
]

I can loop through all nested objects with recursion, but I don’t know how to get that array…

Here is my code:

const data = {
  "1": {
    "2": {
      "3": {
        "4": {},
        "5": {}
      }
    },
    "6": {
      "7": {
        "8": {},
        "9": {
          "10": {
            "11": {},
            "12": {}
          }
        }
      }
    }
  }
}

let list = [];

function iterate(object) {
    if( object !== null && typeof object == "object" ) {
        Object.entries(object).forEach(([key, value]) => {
            if( JSON.stringify(value) != JSON.stringify({})) {
                let obj = {};
                obj[key] = Object.keys(value)
                list.push(obj);
                iterate(value);
            }
        });
    }
}

iterate(data);

Solution – 1

I would first create a recursive function that will iterate the paths in a more intuitive format: each path will be represented as an array of nodes. This function could be a generator function.

Then create a mapping function that converts such path to a list of objects with single key/value pairs, assuming the given path has an even number of nodes.

Finally, use Array.from to consume the iterator returned by the generator function, and use the mapping argument to perform the mapping defined by the second function:

function* iteratePaths(object) {
    const entries = Object.entries(Object(object));
    if (entries.length == 0) return yield [];
    for (const [key, value] of entries) {
        for (const path of iteratePaths(value)) {
            yield [key, ...path];
        }
    }
}

const toPairs = path => 
    path.reduce((acc, val, i) => i % 2 ? [...acc, { [path[i-1]]: val }] : acc, []);

// Example input:
const data = {"1": {"2": {"3": {"4": {},"5": {}}},"6": {"7": {"8": {},"9": {"10": {"11": {},"12": {}}}}}}}
const result = Array.from(iteratePaths(data), toPairs);
console.log(result);