By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
457,938 Members | 2,205 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 457,938 IT Pros & Developers. It's quick & easy.

Detection of a loop in a linked tree (or linked list)

P: n/a
I found that with memory allocating techniques used nowadays
(addresses alignment, eg. on 32bit machines) one can detect loops in a
tree structure very fast, without using extra memory. This is due to a
possibility of storing extra information in unused bits of the tree
pointers (it works for linked lists too). One can say it is dangerous
or obvious, but I haven't seen it anywhere, and maybe it will be
useful for someone.

The procedure of loops detection has two steps:
1. Going through the tree with marking visited nodes (in pointers to
them) and checking if every node was visited only once (visiting node
twice means a loop)
2. Going through the tree once again and fixing tree pointers values,
to get the original tree structure
Below is an example code in C - you need only to add tree creation
function you like.


#include "stdio.h"
#include "ctype.h"
#include "malloc.h"
#define LEAFS 2 //can be any integer >0

typedef struct t { //simple tree structure
int data;
struct t * leafs[LEAFS];
} tree;

* test for cycles in a tree by using pointers reallignment
int TestTreeAl(tree **root)
int i=0;
int j;
tree *p;
if (*root==NULL) return 0;
if (j!=0) return 1; //if a node is marked with odd pointer - cycle
p=*root; //remember the correct pointer
(int)*root=((int)*root)+1; //mark the node
for (i=0; i<LEAFS; i++) //visit all the leafs
if (TestTreeAl(&(p)->leafs[i])==1) return 1;
return 0;

* fix allignment of tree pointers
void FixTree(tree **root)
{ int i,j;
if (*root!=NULL)
if (j!=0)
(int)*root=((int)*root)-1; //unmark previously marked node
for (i=0; i<LEAFS; i++)
if ((j!=0) && ((*root)->leafs[i]!=NULL))

* test linked tree for cycles
* returns 1 if any cycles were detectet, otherwise it returns 0
* (almost no additional memory used, only two visits in each tree
int TestTree(tree *root)
int i=TestTreeAl(&root); //testing for tree cycles with pointers
return i;

* print all the data from the tree (sequence is not important)
void print_tree_data(tree *root)
int i;
if (root!=NULL)
for (i=0; i<LEAFS; i++)

void main()
tree *root;
int i;

printf("* Example of a fast and memory efficient method \n* for
finding cycles in a tree structure (by Maciej Huk)\n\n");

root=NULL; //for NULL tree we will have no cycles
//make_tree(&root); //You need to define this function yourself

print_tree_data(root); //if tree was OK, the print makes no problems


printf("Before adding the cycles: ");
if (i==0) printf("NO CYCLES :)\n");
else printf("CYCLES DETECTED!\n");

* try adding cycles to your tree (beware for the initial tree
//root->leafs[1]->leafs[0]=root->leafs[0]->leafs[1]; //example of a
cycle to try
//root->leafs[0]->leafs[0]->leafs[0]=root; //...and another one


printf("\nAfter adding the cycles: ");
if (i==0) printf("NO CYCLES :)\n");
else printf("CYCLES DETECTED!\n");

if (i==0) print_tree_data(root); //if there is no cycles we can
easily print the tree

printf("\n\nPress any key to exit...");
while (!getch());


Best regards,
Jun 27 '08 #1
Share this question for a faster answer!
Share on Google+

This discussion thread is closed

Replies have been disabled for this discussion.