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;
}

Answer 1

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
}

Answer 2

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);
}