**Background :** In our application we are using a tree structure for representing some logic. The tree may contain another tree as a child node. The requirement was to parse the complete tree structure by traversing it. While traversing the tree, if a child node refers to another tree, we have to parse this child tree node as well.

Eg. suppose we have tree T1 .T1 has child nodes T2 and T3. For creating the logic for T1, we have to parse T2 and T3’s logic and put it into T1.

T1

/ \

T2 T3

Suppose T2 contains child node T4 and T5. Then while creating logic for T1 we have to parse T4 and T5 to build T2 and put in T1.

T2

/ \

T4 T5

On adding logic of T2 in T1.

T1

/ \

T2 T3

/ \

T4 T5

If T2 contains T1 then there will be a cycle present in the tree.

T2

/ \

T1 T5

In this case, we will parse T1 then T2 then T1 then T2 putting the program into an infinite loop.

**T1**

/ \

T2 T3

/ \

**T1** T5

**Problem statement : **We want to create a tree such that, it can add another tree as its child node. There should be no cycle while creating the tree. Hence, we have to find whether a cycle is formed while adding a child to the tree.

**Input : **We have set of trees with no cycle and each child node refers to another tree . We created a tree map to represent the relationship between trees in which the treeMap key represents the tree id and value array represents list of tree id in its child nodes.

**var ****treeMap **= {

**“node1”**: [

**“node4”**,

**“node2”**,

**“node3”**

** **],

**“node2”**: [

**“node4”**

** **],

**“node3”**: [

**“node4”**,

**“node2”**

** **],

**“node4”**:[]

};

In above Map if we add node3 tree in node2 then cycle will be formed .

**Output:** We created function “isCyclePresent” which returns true if cycle is present after adding child node in tree.

Basic idea of algorithm is : a breadth first search begin with node which will be added in given tree. Search will visit every node of the tree exactly once .If we find a node in the child which is same as parent then the is formed

Referred from “Tarjan’s Algorithm”

We have implemented isCyclePresent function using jQuery.

/*function to prevent cycles in tree on adding new node*/

**function **isCyclePresent(startNode, newNode ){

**var **returnValue =**false**; //set return value

**var **queue = []; //to implement queue data structure in javascript

queue.push(newNode); //adding element in queue rare end

**var **queueElement;

**if**( ! $.isEmptyObject(**treeMap**)) {

**while**(queue.**length**!=0){

queueElement= queue.shift(); //removing element from queue front end

//check if start node is equal to it child element

**if**(startNode == queueElement ){

returnValue=**true**; //cycle is present

**break**;

}

//add element to to queue to traverse tree

**if**(**treeMap**[queueElement].length!=0){

$.each(**treeMap**[queueElement],**function**(index,element){

queue.push(element); //adding element in queue rare end

});

}

}

**return **returnValue; //return true if cycle present after adding new node in existing tree

}

**else **{

returnValue=**false**;

}

}

Here is a working example – https://jsfiddle.net/ecnw2azp/1/

**Conclusion** : This is a post demonstrating how we can prevent cyclic dependency while creating a tree. So while parsing tree we can insure program never goes into an infinite loop.