Take the 2-minute tour ×

Given a node with the following structure

class Node {
int data,
Node* P1,
Node* p2;

We need to determine, if the node represents a Circular Doubly Link List OR a Binary Tree. In my opinion We need to start traversing the given node in one direction

node = givenNode;
while(node->P1 != null && node->P1 != givenNode)
  node = node->p1

if(node == givenNode) // It means Circular DLL
else if(node == null)  // It means Tree

And it would take O(n) time to detect this.

Please suggest if there is any better approach than this.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

I suggest you could check if its a doubl-linked list or not with this piece of code:

node = givenNode;
if(givenNode->P1 == null || givenNode->P2 == null)
 // It can not be double link list (circular)
else if(givenNode->p1->p2 == givenNode || givenNode->p2->p1 == givenNode)
//It is a double linked list
It is not a double linked list

And we have O(1) complexity

share|improve this answer
... assuming there's more than one node in the list! (Otherwise it's unsolvable, or both answers are equally valid) –  Emil Vikström Sep 24 '12 at 10:44
@george.zakaryan. Thanks for the quick answer, I have edited the answer to make it bit more accurate, because if we do not add the first check we might get a null pointer exception –  Astric Star Sep 24 '12 at 11:46
add comment

Your Answer


