recursion base case problem

[keicola]

hi. i made a function which is supposed to create a binary tree from preorder and inorder traversals using recursion. i did this by making arrays for the left subtree and the right subtree in preorder and in inorder at each call of the function.

makeNode() puts the data into a node.
findIndex() returns the index of a given character inside the given array.
plantBTree() is supposed to create the binary tree recursively

when i thought about it, at the terminal nodes, the arrays for their left and right subtrees should be of length zero. that's why i made my condition such that the procedure inside the function only work if both preorder and inorder arrays are not equal to zero. since that didn't work, i also tried making my condition like this: if the preorder and the inorder arrays are equal to zero, the function only returns the node. else, it proceeds to executing the procedures inside the function. that didn't work also.

the code i put below was the first one that i did. i can't figure out why it's not working. please help.

node *plantBTree(char inorder[], char preorder[])
{
	root = makeNode(preorder[0]);
	printf("%c\n", root->data);
	
	char LSTi[80];
	char RSTi[80];
	char LSTp[80];
	char RSTp[80];
	
	int InorderIndex = findIndex(inorder,preorder[0]);
	int PreorderIndex = InorderIndex;	

	if ((strlen(inorder) != 0) && (strlen(preorder) != 0)){
		/*Inorder Array for Left Subtree*/
		int li;
		printf("Left Subtree Elements (I): ");
		for(li=0; li<InorderIndex; ++li)
		{
			LSTi[li] = inorder[li];
			printf("%c", LSTi[li]);
		}
		printf("\n");
	
		/*Inorder Array for Right Subtree*/
		int ri;
		int ilen = strlen(inorder);
		printf("Right Subtree Elements (I): ");
		for(ri=InorderIndex+1; ri<ilen; ++ri)
		{
			RSTi[ri] = inorder[ri];
			printf("%c", RSTi[ri]);
		}
		printf("\n");
		
		/*Preorder Array for Left Subtree*/
		int lp;
		printf("Left Subtree Elements (P): ");
		for(lp=1; lp<PreorderIndex+1; ++lp)
		{
			LSTp[lp] = preorder[lp];
			printf("%c", LSTp[lp]);
		}
		printf("\n");
		
		/*Preorder Array for Right Subtree*/
		int rp;
		int plen = strlen(preorder);
		printf("Right Subtree Elements (P): ");
		for(rp=PreorderIndex+1; rp<plen; ++rp)
		{
			RSTp[rp] = preorder[rp];
			printf("%c", RSTp[rp]);
		}
		printf("\n\n");
		
		
		root->LeftNode = plantBTree(LSTi,LSTp);
		root->RightNode = plantBTree(RSTi,RSTp);
		
		
	} return(root);
}

this is the complete code, if you'd like to check:

#include <stdlib.h>
#include <stdio.h>

struct node
{
	struct node *LeftNode;
	char data;
	struct node *RightNode;
}*bago, *root;

node *makeNode(char c);
node *plantBTree(char inorder[], char preorder[]);
int findIndex(char inorder[],char c);

main()
{
	/*
	makeNode('A'); ----- checking makeNode
	printf("%c%c", preorder[3], inorder[1]); ----- checking initialization of arrays
	
	printf("%d\n", findIndex(preorder[3]));
	printf("%d", findIndex('Z')); ----- testing return function of findIndex
	*/
	
	char preorder[] = "PILAR";
	char inorder[] = "LIAPR";
	
	plantBTree(inorder, preorder);
}

node *makeNode(char c)
{
	bago = (node *)malloc(sizeof(node));
	bago->data = c;
	bago->LeftNode = NULL;
	bago->RightNode = NULL;
	/*printf("New Node: %c\n", bago->data);*/
	return (bago);
}

node *plantBTree(char inorder[], char preorder[])
{
	root = makeNode(preorder[0]);
	printf("%c\n", root->data);
	
	char LSTi[80];
	char RSTi[80];
	char LSTp[80];
	char RSTp[80];
	
	int InorderIndex = findIndex(inorder,preorder[0]);
	int PreorderIndex = InorderIndex;	

	if ((strlen(inorder) != 0) && (strlen(preorder) != 0)){
		/*Inorder Array for Left Subtree*/
		int li;
		printf("Left Subtree Elements (I): ");
		for(li=0; li<InorderIndex; ++li)
		{
			LSTi[li] = inorder[li];
			printf("%c", LSTi[li]);
		}
		printf("\n");
	
		/*Inorder Array for Right Subtree*/
		int ri;
		int ilen = strlen(inorder);
		printf("Right Subtree Elements (I): ");
		for(ri=InorderIndex+1; ri<ilen; ++ri)
		{
			RSTi[ri] = inorder[ri];
			printf("%c", RSTi[ri]);
		}
		printf("\n");
		
		/*Preorder Array for Left Subtree*/
		int lp;
		printf("Left Subtree Elements (P): ");
		for(lp=1; lp<PreorderIndex+1; ++lp)
		{
			LSTp[lp] = preorder[lp];
			printf("%c", LSTp[lp]);
		}
		printf("\n");
		
		/*Preorder Array for Right Subtree*/
		int rp;
		int plen = strlen(preorder);
		printf("Right Subtree Elements (P): ");
		for(rp=PreorderIndex+1; rp<plen; ++rp)
		{
			RSTp[rp] = preorder[rp];
			printf("%c", RSTp[rp]);
		}
		printf("\n\n");
		
		
		root->LeftNode = plantBTree(LSTi,LSTp);
		root->RightNode = plantBTree(RSTi,RSTp);
		
		
	} return(root);
}

int findIndex(char inorder[],char c)
{
	int i;
	int len = strlen(inorder);
	/*printf("%d\n", len); ----- testing strlen*/
	for(i=0; i<len; ++i){
		if (inorder[i]==c)
			/*printf("%d",i); ----- testing searching for index*/
			return (i);
	}
	return(-1);
}

[nezachem]

First of all, both arrays must have the same size - they represent the same tree, so they have exactly as many elements as there are nodes in the tree. No need to test both sizes.
Second, in the terminating situation you should return NULL, not the root.

Third, there are way too many problems with the implementation.

You determine the array size with strlen(). This is wrong in general, because it restricts you to zero terminating strings (it also kills the asymptotics, but for now it's a least of the worries). This is wrong in particular, because the copies you made are not zero terminated.
The simplest way around - which also happens to be a correct solution - is to pass the size as a third parameter to plantBTree.

The copies themselves are also made incorrectly. For example,the RSTp loop fills up the right part of the array - leaving the left one with garbage. That garbage is then passed down to the recursive call. You need to pass RSTi + PreorderIndex + 1, RSTp + PreorderIndex + 1 instead, or copy to the beginning of the RST arrays.
Now, with the size being passed separately, copying doesn't buy you anything, and just stands in the way. You shall work directly from the original arrays. Hint: the whole function fits into 10 lines or so.

A final note: get rid of the global variables. They are bad in general, and extremely bad in the context of recursion.

[keicola]

thank you very much!
i read this late but these were pretty much all that i changed.
my program works now :D