1
To detect if there is a loop in Binary Tree.

I think we can do inorder traversal and mark each and every node visited and if we again come across to any of such node which is visited then we can say that there is a loop in Binary Tree.

It will take O(logn) - Time O(n) - Auxiliary Space

Are there any more efficient methods for this?

Luv
  • 5,381
  • 9
  • 48
  • 61
  • 1
    Pretty sure a tree is loopless by definition... no? – andersoj May 17 '12 at 01:25
  • 2
    @andersoj: this kind of question comes up all the time with intro programming or interview situations as a way to test troubleshooting and knowledge of the datastructures in question... – sarnold May 17 '12 at 01:31
  • @andersoj Are binary Trees loopless by definition? – Luv May 17 '12 at 01:33
  • 2
    @Luv: A tree is a graph which, among other equivalent things, is both connected and cycle-free. A loop is a (trivial) cycle. So yes, a tree (and more specifically, a binary tree) is by definition loopless. HOWEVER, you might want to be able to verify this invariant. To do so, you must forget that the data structure is supposed to be a tree because, if there's a loop, who knows what other assumptions are broken? – andersoj May 17 '12 at 01:55
  • possible dupe: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph – andersoj May 17 '12 at 02:22
  • possible duplicate of [Efficient algorithm to determine if an alleged binary tree contains a cycle?](http://stackoverflow.com/questions/7140215/efficient-algorithm-to-determine-if-an-alleged-binary-tree-contains-a-cycle) – Ryan Bigg Oct 30 '12 at 20:27

0 Answers0