DEPTH OF AN N-ARY TREE AND FINDING ROUTE TO A NODE IN AN N-ARY TREE
This article is originally published in Golibrary Co
Depth of an N-Ary tree and Finding Route to a node in an N-Ary tree
Problem Statement:- Given an N-Ary tree, how to find it’s depth and trace route to a destination from a source node of the tree.
Consider the below N-Ary tree. In this example, we have used JSON object which contains all the hierarchical representations of an N-Ary tree and thus the traversing algorithm and route tracing algorithms are according to the JSON structure.
Click here to see the demo
The JSON that represents this tree is:
[{
head: '1',
id: 'aa',
contents: 'Node1',
children: [
{
head: '2',
id: 'a1',
contents: 'Node1-Child',
children: [
{ head: '2.3', id: 'a11', contents: 'Node1.1-Child', children:[{ head: '2.4', id: 'a12', contents: 'Node1.2-Child' },
{ head: '2.5', id: 'a13', contents: 'Node1.3-Child' }] }
]
},
{
head: '3',
id: 'a3',
contents: 'Node1-Child',
children: [
{ head: '3.3', id: 'a121', contents: 'Node3.1-Child', children:[{ head: '3.4', id: 'a122', contents: 'Node3.2-Child' },
{ head: '3.5', id: 'a133', contents: 'Node3.3-Child' }] }
]
},
{
head: '4',
id: 'a2',
contents: 'Node1.2-Child',
children: [
{ head: '5', id: 'a21', contents: 'Node1.2.1-Child', children:[{head: '5.1', id: 'a245', contents: 'Node1.2.1.1-Child'}]},
{ head: '6', id: 'a22', contents: 'Node1.2.2-Child', children:[{head: '6.1', id: 'a2454', contents: 'Node1.2.1.2-Child',
children:[{head: '6.2', id: 'a24445', contents: 'Node1.2.1.4-Child',
children:[{ head: '6.3', id: 'a1341', contents: 'Node6.2-Child'}]},
]}]}
]
}
]
}];
Algorithm for finding depth of tree:
Loop through the JSON array and check each Key:Value pair for data type array/object.
Recursively invoke the JSON traversing till the last item of JSON array is reached for each such child array obtained in Step 1. Each child array here represents a level of N-Ary tree. Store the levels here for each such child array which represents children of a parent node at a level N.
3.For each JSON object, iterate through the JSON key attributes and recursively invoke JSON traversing for each property in JSON child object be it of type array or object.
4.Once there are no more arrays in Step 2 and no objects/arrays within the parent JSON object, increment the height obtained from step 2 by 1 for accommodating the root of the tree and return it and exit.
Below is the JS code for this algorithm:
function calcHeight(theObject, height) {
if (theObject instanceof Array) {
for (var i = 0; i < theObject.length; i++) {
//console.log("Node = ", theObject[i].head, "Node Level = ", height);
heightOfTree = height;
calcHeight(theObject[i], height);
}
} else {
for (var prop in theObject) {
if (theObject[prop] instanceof Object || theObject[prop] instanceof Array) {
calcHeight(theObject[prop], ++height);
}
}
}
return heightOfTree + 1;
}
Algorithm for tracing route to destination from source node:
This reuses the previous algorithm logic to a large extent. Using previous algorithm, obtain a map of Node and the level at which the Node is based.
Use the NodeMap from step 1 to find the destination node in the map and save its level.
Iterate backwards, through NodeMap again from the index where destination is found. Keep decrementing by one and collect all nodes where the levels are in descending order.
Repeat step 3 until root node and slice the collection until destination node by looking up source node in the path obtained as a result of step 3 and 4. Return the sliced collection which will have the path from source to destination in case, if they are directly connected.
If there is no direct connectivity between source and destination , then trace route from source till the root and from root till destination and concatenate the results. If there are repeating nodes in this path, get rid of duplicate such nodes and return the final result. If that’s not the case, return concatenated results as is.
Also Read: https://www.golibrary.co/finding-diameter-of-a-binary-tree/
Below is the Algorithm for extracting shortest path from a given path:
function findShortestPath(path) {
var index1, index2, arr1, arr2;
for (i = path.length - 1; i >= 0; i--) {
for (j = i - 1; j >= 0; j--) {
if (path[i] === path[j]) {
index1 = i;
index2 = j;
arr1 = path.slice().slice(0, index2);
arr2 = path.slice().slice(index1, path.length);
return arr1.concat(arr2);
}
}
}
return null;
}
JS code for the above algorithm is as below:
function getRoute() {
var source = document.getElementById("source").value,
destination = document.getElementById("destination").value;
var path = traceRoute(source, destination);
if (path instanceof Array) {
document.getElementById("route").innerHTML = "
Route from Nodes : " + source + " to " + destination + " is :
" + path.join("->") + "
";
} else if (path === -1) {
document.getElementById("route").innerHTML = "
Invalid Input : Either of the Nodes, " + source + " or " + destination +
" you entered doesn't exist in the tree!!
";
} else {
document.getElementById("route").innerHTML = "
Node " + destination + " isn't reachable from Node " + source + "
";
}
}
function traceRoute(source, destination) {
var routes = findRoute(jsonObject, 0),
pivot = -1,
spivot = -1;
for (var index = 0; index < routes.length; index++) { if (destination === routes[index].node) { pivot = index; } if (source === routes[index].node) { spivot = index; } } if (pivot === -1 || spivot === -1) { return -1; } var path = routes[pivot].node; var level = routes[pivot].level; while (pivot > 0) {
pivot--;
if (level - routes[pivot].level === 1) {
path += "|" + routes[pivot].node;
level = routes[pivot].level;
}
}
var routeArr = path.split("|").reverse();
if (routeArr.some(function(item, index) {
if (item === source) {
routeArr = routeArr.splice(routeArr.indexOf(source), routeArr.length);
return true;
}
})) {
return routeArr;
} else {
// try finding shortest path first if it exists
//var finalRoute = findShortestPath(source, destination);
// else try again here as nodes could be reachable via root and shortest path is not found
var route1 = traceRoute(routeMap[0].node, source).reverse();
var arr = traceRoute(routeMap[0].node, destination);
var route2 = (routeMap[0].node === destination) ? [] : arr.slice(1, arr.length);
var finalPath = route1.concat(route2);
var shortestPath = findShortestPath(finalPath);
if (shortestPath) {
return shortestPath;
} else {
return route1.concat(route2);
}
}
}
function findRoute(theObject, height) {
if (theObject instanceof Array) {
for (var i = 0; i < theObject.length; i++) {
console.log("Node = ", theObject[i].head, "Node Level = ", height);
var object = {
"node": theObject[i].head,
"level": height
};
routeMap.push(object);
findRoute(theObject[i], height);
}
} else {
for (var prop in theObject) {
if (theObject[prop] instanceof Object || theObject[prop] instanceof Array) {
findRoute(theObject[prop], ++height);
}
}
}
return routeMap;
}
This article was originally published on :- https://www.golibrary.co/depth-route-node-n-ary-tree/
Hope you enjoyed reading this. Like us on https://www.facebook.com/golibraryco &
https://linkedin.com/company/golibrary for more interesting reads like this.