How to get the tree path recrusively?

3106 views javascript
2

Here I have nodes and corresponding edges in JSON format. I want get the path from root to the leaf recursively. I tried using the following code but I'm not getting the exact result.

let node0 = [];
let initPath = '0';
let iterateObject = (data) => {
    if (Object.keys(data.edges).length === 0) {
        node0.push(initPath);
        initPath = '0';
    } else {
        Object.keys(data.edges).forEach((edge, index) => {
            initPath += "->" + edge;
            console.log(edge + " : " + index);
            iterateObject(data.edges[edge]);

        });
    }
};

iterateObject(data);
Current Output: 

[ "0->1->3", "0->5", "0->2->5" ]

For testing purpose I tried the following JSON. Here 0 and 6 are root nodes and I'm trying to call the edges recursively for finding the path.

{
    "0": {
        "edges": {
            "1": {
                "edges": {
                    "3": {
                        "edges": {}
                    },
                    "5": {
                        "edges": {}
                    }
                }
            },
            "2": {
                "edges": {
                    "5": {
                        "edges": {}
                    }
                }
            }
        }
    },
    "6": {
        "edges": {
            "2": {
                "edges": {
                    "5": {
                        "edges": {}
                    }
                }
            }
        }
    }
}
Expected Output: 

["0->1->3","0->1->5","0->2->5", "6->2->5"]

answered question

1 Answer

8

You could take an iterative and recursive approach by checking the nested objects.

function getPathes(object) {
    var result = [];
    Object
        .entries(object)
        .forEach(function iter(keys) {
            return function ([key, { edges }]) {
                var entries = Object.entries(edges);
                if (entries.length) {
                    return entries.forEach(iter(keys.concat(key)));
                }
                result.push(keys.concat(key).join('->'));
            };
        }([]));
    return result;
}

var tree = { 0: { edges: { 1: { edges: { 3: { edges: {} }, 5: { edges: {} } } }, 2: { edges: { 5: { edges: {} } } } } }, 6: { edges: { 2: { edges: { 5: { edges: {} } } } } } };

console.log(getPathes(tree));

posted this

Have an answer?

JD

Please login first before posting an answer.