I have an insertion function for a BST, which also calls and checks if a node is balanced. If it is not I call rotation function on the node. This is where the problem is -> up till then my program worked fine, however, after adding that function my program throws out errors. I have only written the leftrotate function for now because I am testing on a case that only requires left rotation, therefore the rightrotate now being there is not the problem for now. This is my insertion function
Tnode* insertnode(Tnode* root, int key)
{
if (root == NULL)
{
Tnode* child = (Tnode*)malloc(sizeof(Tnode));
child->left = NULL;
child->right = NULL;
child->key = key;
child->balance = 0;
return child;
}
if (root->key < key)
{
root->right = insertnode(root->right,key);
}
else if (root->key >= key)
{
root->left = insertnode(root->left,key);
}
if (balance(root) > 1 || balance(root) < -1)
{
if (balance(root) == -2)
{
*edit* root = leftrotate(root);
}
else
{
//rightrotate(root);
}
}
return root;
}
The criteria for balance is this: the absolute difference between the left subtree and right subtree of a node must not be greater than 1. This is my left rotate function:
*edit*Tnode* leftrotate(Tnode *root)
{
Tnode * temproot = root;
root = root->right;
root->left = temproot;
temproot->right = NULL;
return root; *edit*
}
This is the function that frees the tree:
void freetree(Tnode * root)
{
if(root == NULL)
{
return;
}
freetree(root->left);
freetree(root->right);
free(root);
return;
However, all blocks are not freed and the tree doesnt seem to balance itself correctly. This is the valgrind report:
==3704== HEAP SUMMARY:
==3704== in use at exit: 192 bytes in 8 blocks
==3704== total heap usage: 11 allocs, 3 frees, 808 bytes allocated
==3704==
==3704== LEAK SUMMARY:
==3704== definitely lost: 96 bytes in 4 blocks
==3704== indirectly lost: 96 bytes in 4 blocks
==3704== possibly lost: 0 bytes in 0 blocks
==3704== still reachable: 0 bytes in 0 blocks
==3704== suppressed: 0 bytes in 0 blocks
==3704== Rerun with --leak-check=full to see details of leaked memory
==3704==
==3704== For counts of detected and suppressed errors, rerun with: -v
==3704== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
What am I doing wrong ? Any tips? Edit: minimal main, file I'm opening is a binary file. 'i' refers to instruction to insert.
FILE *fp2 = fopen(argv[2],"rb");
if (fp2 == NULL)
{
printf("%d\n",-1);
return EXIT_FAILURE;
}
int key = 0;
char placeh;
Tnode * root = (Tnode*)malloc(sizeof(Tnode));
fread(&root->key,sizeof(int),1,fp2);
root->left = NULL;
root->right = NULL;
root->balance = 0;
fread(&placeh,sizeof(char),1,fp2);
while (1)
{
fread(&key,sizeof(int),1,fp2);
fread(&placeh,sizeof(char),1,fp2);
if (feof(fp2))
{
break;
}
if (placeh == 'i')
{
//printf("%d ",key);
insertnode(root,key);
}
}
printtree(root);
freetree(root);
fclose(fp2);
}
return EXIT_SUCCESS;
}