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.

Advertisements