Can somebody help me debug this code??

A

antarcticprince

Disciple
This C program creates a tree from its given preorder and inorder traversal.... the problem is it is going into infinite looping inspite of the dry run working properly..please help...

#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
int key;
struct tree * left;
struct tree * right;
}Tree;

Tree * createTreeFromPreorderInorder(int preorder[],int inorder[],int left,int right, int pos)
{
int index;
if(left > right)
{
return NULL;
}
Tree *t = (Tree*)malloc(sizeof(Tree));
t->key = preorder[pos];
index = search(inorder,left, right, t->key);
t->left = createTreeFromPreorderInorder(preorder,inorder ,left,index-1, pos+1 );
t->right = createTreeFromPreorderInorder(preorder,inorder,index +1, right, pos+1+(left+index));
return t;
}

int search(int arr[],int left, int right,int key)
{
int i;
for(i=left; i <= right; i++)
{
if( key == arr)
{
return i;
}
}
return -1;
}

void display(Tree *t,int level)
{
int i;
if(t)
{
display(t->right, level+1);
printf("\n");
for(i=0;i<level;i++)
printf("\t");
printf("%c\t", t->key);
display(t->left, level+1);
}
}
int main()
{
int preorder[] = {'A', 'B' , 'D', 'E', 'F', 'C', 'G', 'H', 'J','L','K'};
int inorder[] = {'D', 'B','F','E','A','G','C','L','J','H','K'};
Tree *newTree = createTreeFromPreorderInorder(preorder,inorder,0,10,0);
display(newTree,1);
getch();
return 0;
}
 
I can try and help, although it's been a long time since I used C (11 years to be exact :p). But, you'll have to provide the right source. Maybe you should try embedding your source in [ CODE ] [ /CODE ] tags. I clearly see that the line:

Code: 
Tree *newTree = createTreeFromPreorderInorder(preorder,inorder,0,1 0,0);

will not compile as there's a comma missing after the 1. Maybe there are more such errors.

Also please share a link where I can download Turbo C.
 
I am unable to fully understand the working of the recursive function but made a few changes to your code so that you can probably debug it yourself.

The search() function returns a value of -1 but you have not checked for that condition.
Once I added that the looping has stopped but the entire array is not getting parsed.
That happens due to pos value being passed as 17 at one point of time.
I have added a couple of printf statements to help you with the debugging. If you do not have access to a proper IDE/runtime-debugging then printf is your best friend. Use them everywhere.

Also, you have not freed the memory allocated using malloc. Even though this is a very basic program, please be careful when using memory allocation functions. Added that to the code too.

If you can point out to the theory/algorithm which you used to code this program, I can help you figure out the error in recursion if there is any.

Code: 
#include<stdio.h>
#include<stdlib.h>
typedef struct tree
{
	int key;
	struct tree * left;
	struct tree * right;
}Tree;
int search(int arr[],int left, int right,int key);
void display(Tree *t,int level);
Tree *root = NULL;

Tree * createTreeFromPreorderInorder(int preorder[],int inorder[],int left,int right, int pos)
{
	int index;
	printf("func called with left = %d, right = %d, pos = %d\n", left, right, pos);
	if(left > right)
	{
		return NULL;
	}
	Tree *t = (Tree*)malloc(sizeof(Tree));

	t->left = NULL;
	t->right = NULL;

//	if(root == NULL)
//		root = t;
//	display(root, 0);	
//	getch();
	t->key = preorder[pos];
	printf("adding %c\n",t->key);
	index = search(inorder,left, right, t->key);
	if (index == -1)
	{
		return NULL;
		free(t);
	}
	t->left = createTreeFromPreorderInorder(preorder,inorder ,left,index-1, pos+1 );	
	t->right = createTreeFromPreorderInorder(preorder,inorder,index +1, right, pos+1+(left+index));	
	return t;
}

int search(int arr[],int left, int right,int key)
{
	int i;
	for(i=left; i <= right; i++)
	{
		if( key == arr[i])
		{
			return i;
		}
	}
	return -1;
}

void display(Tree *t,int level)
{
	int i;
	if(t)
	{
		display(t->right, level+1);
		printf("\n");
		for(i=0;i<level;i++)
			printf("\t");
		printf("%c\t", t->key);
		display(t->left, level+1);
	} 
}

void freetree(Tree *t)
{	
	if (t->left != NULL)
		freetree(t->left);
	if (t->right != NULL)
		freetree(t->right);
	if(t->left == NULL && t->right == NULL)
	{
		free(t);
		t = NULL;
	}
}
int main()
{
	int temp;
	int preorder[] = {'A', 'B' , 'D', 'E', 'F', 'C', 'G', 'H', 'J','L','K'};
	int inorder[] = {'D', 'B','F','E','A','G','C','L','J','H','K'};
	Tree *newTree = createTreeFromPreorderInorder(preorder,inorder,0,10,0); 
	display(newTree,0);
	freetree(newTree);
	getch();
	return 0;
}
 
In case anyone is interested, the recursion works as follows,

Code: 
        A
      /   \
     B     C
    / \   / \
   D   E G   H
      /     / \
     F     J   K
          /
         L

Pre-order: {'A', 'B' , 'D', 'E', 'F', 'C', 'G', 'H', 'J','L','K'}
In-order: {'D', 'B','F','E','A','G','C','L','J','H','K'}

If you scan the pre-order array from left to right, you get the successive root elements. e.g. A is the root of the tree. You can then search for A in the in-order array. Every element to the left of A in the in-order array goes to A's left subtree, and every element to the right goes to A's right subtree.

Code: 
              A
(D B F E)           (G C L J H K)

You can recurse now on both the left and right subarrays. If you take the left subarray, the next element from the pre-order array 'B' - is the root. As before, every element to the left of 'B' in the in-order array is part of B's left subtree, and vice versa.

Code: 
                  A
       B                      C
(D)        (F E)      (G)          (L J H K)

This way, given a pre-order or post-order AND an in-order traversal, you can always reconstruct the binary tree.
 
Back
Top