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

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