Malloc stack overflow

Question

Guys below code works fine until size= 100000. However it gives me stack overflow error after size=200000. How can i fix that ? Is there some way to optimize it ?

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define SIZE 500000
// HELPER ARRAY FUNCTIONS
void check(int *arr)
{
    int i = 0;
    for (i = 0; i < SIZE - 1; i++)
    {
        if (arr[i]>arr[i + 1])
        {
            printf("Not sorted.\n");
            return;
        }
    }
    printf("Sorted.\n");
}
void fill_array(int *arr)
{
    int i = 0;
    for (i = 0; i < SIZE; i++)
        arr[i] =rand()%100;
}
void print_array(int *arr)
{
    int i;
    for (i = 0; i < SIZE; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
// NODE STRUCT
typedef struct BST_NODE
{
    struct BST_NODE *left, *right;
    int data;
}node;
// TREE FUNCTIONS
node* generate_node(int *value)
{
    node *n = (node*)malloc(sizeof(node));
    n->left = NULL;
    n->right = NULL;
    n->data = *value;
    return n;
}
node* insert_node(node *n, int *value)
{
    if (n == NULL)
        return generate_node(value);
    if (*value < n->data)
        n->left = insert_node(n->left, value);
    else
        n->right = insert_node(n->right, value);
    return n;
}
node* construct_BST(int *arr, node* n)
{
    int i;
    n = NULL;
    for (i = 0; i < SIZE; i++)
        n = insert_node(n, &arr[i]);
    return n;
}
int s = 0;
void LVR(int *arr, node* n)
{
    if (n != NULL)
    {
        LVR(arr, n->left);
        arr[s] = n->data;
        s++;
        LVR(arr, n->right);
    }
}
void tree_sort(int *arr)
{
    node *root = (node*)malloc(sizeof(node));
    root = construct_BST(arr, root);
    LVR(arr, root);
}
// DRIVER PROGRAM
int main()
{
    int *Array = (int*)malloc(sizeof(int)*SIZE);
    fill_array(Array);
    tree_sort(Array);
    print_array(Array);
    check(Array);
    free(Array);
    getchar();
    return 0;
}

It gives an error at this part below:

node* generate_node(int *value)
{
    node *n = (node*)malloc(sizeof(node));
    n->left = NULL;
    n->right = NULL;
    n->data = *value;
    return n;
}

"Malloc stack overflow" - malloc allocates memory on the heap, it returns a pointer to the allocated memory chunk. If it fails, it returns 0 (NULL). You better check the malloc's return value before using it. Stack overflow has nothing to do with malloc. So what error exactly do you get? — Alex Lop.
– Alex Lop., Commented Apr 17, 2017 at 17:15
Thank you for your comments, @AlexLop yes the exact error is stack overflow as visual studio tells me. This is why i'm stuck — Egeberk Ö.
– Egeberk Ö., Commented Apr 17, 2017 at 17:19
You should consider checking if malloc succeeded: stackoverflow.com/questions/5607455/… — schil227
– schil227, Commented Apr 17, 2017 at 17:22
It is probably an overflow on the only recursive stack operation in this code during tree-build, namely the insert_node invokes. I'd check your logic there. — WhozCraig
– WhozCraig, Commented Apr 17, 2017 at 17:25

BLUEPIXY · Accepted Answer · 2017-04-17 18:55:09Z

As already pointed out by other people, the problem is that the depth of the tree will be SIZE in the worst case.

In the case of your code, since the value to hold is a value less than 100, you can suppress the depth of the tree by not creating a new node for the same value.

In case of the same value change to count up as follows.

#include <stdio.h>
#include <stdlib.h> //stdlib.h include malloc and free

#define SIZE 500000


typedef struct BST_NODE {
    struct BST_NODE *left, *right;
    int data;
    int count;//Add for count
} node;

node* generate_node(int value){//just use int
    node *n = (node*)malloc(sizeof(node));//C does not need to cast from  void *.
    n->right = n->left = NULL;
    n->data = value;
    n->count = 1;//set 1 at first time
    return n;
}

node* insert_node(node *n, int value){
    if(n == NULL)
        return generate_node(value);
    if(value < n->data)
        n->left = insert_node(n->left, value);
    else if (value > n->data)
        n->right = insert_node(n->right, value);
    else
        n->count++;//Add count up
    return n;
}

node* construct_BST(int *arr){//no need node *n as argument 
    int i;
    node *n = NULL;
    for (i = 0; i < SIZE; i++)
        n = insert_node(n, arr[i]);
    return n;
}

int s = 0;
void LVR(int *arr, node *n){
    if (n != NULL){
        int i;
        LVR(arr, n->left);
        for(i = 0; i < n->count; ++i)
            arr[s++] = n->data;//Repeat as many times as count
        LVR(arr, n->right);
    }
}

void tree_free(node *n){
    if(n){
        tree_free(n->left);
        tree_free(n->right);
        free(n);
    }
}

void tree_sort(int *arr){
    node *root = construct_BST(arr);
    s = 0;//Necessary for different calls
    LVR(arr, root);
    tree_free(root);//release tree
}

dbush · Accepted Answer · 2017-04-17 17:37:59Z

If you're getting a stack overflow, that means your function call stack is getting too deep. That can happen when building a binary search tree if the tree ends up being unbalanced.

Best case, your tree height will be O(log n), worst case it will be O(n). If you place items into the tree in sorted order, your binary tree will degenerate into a linked list and you'll hit the worst case.

For this particular example, you're generating random numbers from 0 to 99. You might get more randomize results if you increase the range of the numbers. So instead of using rand()%100, use something like rand()%10000. That might help keep the height of the tree down.

On an unrelated note, you have a memory leak. First, the initial node you allocate for the root of the tree gets overwritten, so you don't need it. Second, you never bother to free the tree structure.

You can take care of these as follows:

void free_tree(node *root)
{
    if (root) {
        free_tree(root->left);
        free_tree(root->right);
        free(root);
    }
}

void tree_sort(int *arr)
{
    node *root = NULL
    root = construct_BST(arr, root);
    LVR(arr, root);
    free_tree(root);
}

Collectives™ on Stack Overflow

Malloc stack overflow

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related