## Detecting Infinite Loop

Just yesterday I have come across a problem at work. The problem is the possible occurrence of infinite loop inside a tree structure. To solve it, I need to come up with an algorithm to detect infinite loop occurrence. This little puzzle brings back the memory of a similar and simpler puzzle my high school computer science instructor asked the class.

The problem was: Given an uni-directional linked list, detect infinite loop without using any extra data structure.

The linked list data structure is really simple:
Node.java

```class Node {
Node next;
}
```

My solution to the problem was something like:
Function isInInfiniteLoop

```boolean isInInfiniteLoop(Node node) {
if (node == null) {
return false;
}
Node turtle = node; // slower moving node
Node rabbit = node.next; // faster moving node
while (rabbit != null) {
if (rabbit.equals(turtle)) {
// the faster moving node has caught up with the slower moving node
return true;
} else if (rabbit.next == null) {
// reached the end of list
return false;
} else {
turtle = turtle.next;
rabbit = rabbit.next.next;
}
}
// rabbit reached the end
return false;
}
```

Simple, isn’t it! At the first glance, almost everyone wondered if this short piece of code is really up to the task. The logic behind it is analogous to having two runners, one (rabbit) running faster than the other (turtle) and, if the course is circular, the faster runner eventually overlapping the slower runner.

Note that it is important for the slower runner to keep moving instead of remaining at the same node because we don’t know where the course will merge into circle. If the merge point is further down the course, the non-moving runner will never enter the loop which the faster runner is lapping.

This algorithm is not only simplistic, it is also efficient. It is just a O(N) or linear function.

Now, getting back to my work related problem, the data structure I am facing is a tree instead of a sequential linked list. The structure is something like:
TreeNode.java

```class TreeNode {
TreeNode parent;
List children;
}
```

I have had a hard time figuring out how to apply my little rabbit and turtle algorithm into this context. When it comes to tree structure, I always think recursion. However, I cannot imagine transforming my algorithm into a recursive algorithm. It just appears overwhelming.

Then, it suddenly hits me, since TreeNode can traverse to its parent, luckily, I could do it backwards. The traversal from child to parent is just another sequential linked list.

It simply feels awesome to see that this little algorithm I thought of years ago is still useful today.

### 21 Responses to “Detecting Infinite Loop”

1. Anurag Garg Says:

dats fine…but how can we remove the loop from the link list(in some efficient manner..)

2. An alternative way is to use treat the tree like a directed graph [D = (N,A); N= nodes, A = arcs] and then apply a Topological Ordering to the nodes. This algorithm has an O(|N|) runtime.

Let D’ be a new graph with D’ = (N’, A) where N’ initially contains all nodes.

i := 1
while there exists a Node v with no parents,
label the node as i
i++
delete v from N’ and all the outgoing arcs in D’
end while

If after |N| iterations, N’ is not empty, then you know you have a directed cycle.

3. To Anurag Garg:
To break the infinite loop, we need to find the link that causes it. The causing link should be the first link that points to an already traversed node. My algorithm however does not pinpoint the causing link.

I’m afraid I can’t yet come up with an easy and efficient algorithm to do that. I know a more complex algorithm that can pinpoint the causing link but require an O(N^2) operation. I’m not sure if that’s efficient enough for you.

4. To Rod:
The problem only gives us the starting node. That means we wouldn’t have N’ (where it contains all nodes). Your solution also suggests using an extra data structure D’ for record keeping, which the problem says not to use.

5. What you’ve discovered is called Floyd’s cycle-finding algorithm and is used in Pollard Rho factorization because the self loops make a Rho looking shape

6. To Jack:
Thanks a lot for the info!
–It is sometimes called the “tortoise and the hare”-algorithm.–
WOW! even the metaphor is the same.
It’s nice to know there is a official name and proven algorithm for this.

7. Hi Eddie,
As far as my understanding of your algorithm goes, this can effectively detect loops of size 1. For eg. lets say the 10th node points to the 11th node which points back to the former and creates an infinite loop.

I have a problem wherein I do not know the size of the loop ( may involve 2 nodes, 10 nodes or 20 nodes or whatever) and I
do not know the starting node that causes the infinite loop.
Can your algorithm be extended to resolve my problem? Please explain. Thanks.

Actually this algorithm can detect loops of any number of nodes, not necessarily just size of 1.
You can try drawing linked lists having loops composed by different number of nodes (2, 10, or 20) and tracing the steps manually.
I think it’s more visible and easier to understand the algorithm this way.
Please give it a try and if you have any question, let me know!

• The easiest way to understand the algorithm is to use two key insights:
1) if a cycle exists, the faster runner/hare/rabbit is (kind of) behind the turtle when the turtle crosses the cycle’s endpoint.
2) the turtle advances one step and the rabbit two, so the rabbit gets one step closer to the turtle every iteration.

Clearly, the size of loop is insignificant. As the rabbit only closes in by one step every iteration, it can’t jump over the turtle at any point.

9. Hi, there is a small bug in your code. When it is not cyclic, rabbit.next.next can give you a nullpointer exception if the length is odd.

• No, it can’t because you just checked rabbit.next in the previous else clause.

• ah, right, didn’t see that.

10. Hi! I was surfing and found your blog post… nice! I love your blog. :) Cheers! Sandra. R.

11. tszming Says:

Tree must be acyclic, else it is a graph.

:)

• good point, thanks

12. Sudarshan Says:

The logic is very simple,clear and easy to implement and maintain.

Thanks
Sudarshan

13. This explanation is too good. This was the question I was asked today in my interview and I couldn’t answer :(

14. Hi, I know this has been written long time ago, but I don’t get clearly how the algorithm works on the tree by going backwards.

The node in which the loop goes ( the one that has two parents or pointed by two other nodes) would have refreshed his parent reference?

Or am I getting things wrong?

15. […] Floyd’s Cycle Detection or the tortoise and the hare or the rabbit and the turtle. […]

16. Hello webmaster do you need unlimited articles for your website ?
What if you could copy content from other blogs, make
it unique and publish on your website – i know the right
tool for you, just search in google:
kisamtai’s article tool

17. […] or “the turtle and the rabbit algorithm”. I found some examples in languages such as Java and Python but nothing using PHP, then I did it by my own based on what I saw. The result code is […]