Hudixt Hudixt - 1 month ago 10
C Question

Sample Implementation of Binary Trees doesn't work for large number of values

I have recently trying to implement a binary tree, it seems to work for less than 1000 values, but after that eventually it gives me stack overflow error

#include<iostream>
#include<math.h>

using namespace std;
struct Node{
long long int val;
Node *left;
Node *right;
};
struct BinaryTree{
Node *head = (Node*) malloc(sizeof(Node));
bool headSet = false;
Node* findLast(Node *asgn,int val){
if (val > asgn->val){
if (asgn->right != NULL)
asgn = findLast(asgn->right, val);
else
return asgn;
}
else{
if (asgn->left != NULL)
asgn = findLast(asgn->left, val);
else
return asgn;
}
return asgn;
}
void insert(long long int vals){
if (headSet){
Node *asgn = (Node*) malloc(sizeof(Node));
asgn = findLast(head,vals);
Node *fix = (Node*)malloc(sizeof(Node));
fix->val = vals;
fix->left = NULL;
fix->right = NULL;
if (vals > asgn->val){
asgn->right = fix;
asgn->left = NULL;
}
else{
asgn->right = NULL;
asgn->left = fix;
}
}
else{
head->val = vals;
head->right = NULL;
head->left = NULL;
headSet = true;
}
}
};
int main(){
BinaryTree a;
for (long long int i = 0; i < 100;i++)
a.insert(i);

return 0;
}


For example:-
If i change

for (long long int i = 0; i < 100;i++)
a.insert(i);


to

for (long long int i = 0; i < 10000;i++)
a.insert(i);


It gives me error. I can't seem to understand why this is happening, where the stack overflows?

Answer

Your stack overflow comes from your findLast method, once the binary tree becomes too big the recursion becomes too much and overflows the call stack at one point. You should convert it into a non-recursive method by storing information about the search in some kind of structure and dynamically allocating that so that your stack doesn't fill up.

P.S use new instead of malloc in C++ and delete to clear up allocated memory, you're currently leaking memory.

Comments