0 / 1087

## 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.

### DEMO here:- Give it a go

The JSON that represents this tree is :-

### Algorithm for finding depth of tree:

1. Loop through the JSON array and check each Key:Value pair for data type array/object.

2. 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:

 12345678910111213141516 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; }