AVL tree implementation in C I have an assignment for which I need to write an AVL tree. This is what I have written so far. It works on all of my tests, but suddenly fails in checking system with TL (time limit exceeded).

Personally I think there could be a bug with input data in test (although I have already solved this problem with Cartesian tree).

struct node
{
    int key;
    int data;    

    int height;

    struct node* left;
    struct node* right;
};

typedef struct node node;

node* new_node(int key, int data)
{
    node* p = malloc(sizeof(*p));

    p -&gt; key    = key;
    p -&gt; data   = data;
    p -&gt; height = 1;
    p -&gt; left   = NULL;
    p -&gt; right  = NULL;

    return p;
}

int max(int a, int b)
{
    return a &gt; b ? a : b;
}

int height(node* p)
{
    return p ? p -&gt; height : 0;
}

void recalc(node* p)
{
    p -&gt; height = 1 + max(height(p -&gt; left), height(p -&gt; right));
}

node* rotate_right(node* p)
{
    node* q = p -&gt; left;

    p -&gt; left = q -&gt; right;
    q -&gt; right = p;

    recalc(p);
    recalc(q);

    return q;
}

node* rotate_left(node* p)
{
    node* q = p -&gt; right;
    p -&gt; right = q -&gt; left;
    q -&gt; left = p;

    recalc(p);
    recalc(q);

    return q;
}

node* balance(node* p)
{
    recalc(p);

    if ( height(p -&gt; left) - height(p -&gt; right) == 2 )
    {
        if ( height(p -&gt; left -&gt; right) &gt; height(p -&gt; left -&gt; left) )
            p -&gt; left = rotate_left(p -&gt; left);
        return rotate_right(p);
    }
    else if ( height(p -&gt; right) - height(p -&gt; left) == 2 )
    {
        if ( height(p -&gt; right -&gt; left) &gt; height(p -&gt; right -&gt; right) )
            p -&gt; right = rotate_right(p -&gt; right);
        return rotate_left(p);
    }

    return p;
}

node* search(node* p, int key)
{
    if ( !p )
        return NULL;

    if ( key &lt; p -&gt; key )
        return search(p -&gt; left, key);
    else if ( key &gt; p -&gt; key )
        return search(p -&gt; right, key);
    else
        return p;        
}

node* insert(node* p, int key, int data)
{
    if ( !p )
        return new_node(key, data);

    if ( key &lt; p -&gt; key )
        p -&gt; left = insert(p -&gt; left, key, data);
    else if ( key &gt; p -&gt; key )
        p -&gt; right = insert(p -&gt; right, key, data);
    else 
        p -&gt; data = data;

    return balance(p);
}

node* find_min(node* p)
{
    if ( p -&gt; left != NULL )
        return find_min(p -&gt; left);
    else
        return p;
}

node* remove_min(node* p)
{
    if ( p -&gt; left == NULL )
        return p -&gt; right;

    p -&gt; left = remove_min(p -&gt; left);
    return balance(p);
}

node* remove_item(node* p, int key)
{
    if ( !p )
        return NULL;

    if ( key &lt; p -&gt; key )
        p -&gt; left = remove_item(p -&gt; left, key);
    else if ( key &gt; p -&gt; key )
        p -&gt; right = remove_item(p -&gt; right, key);
    else
    {
        node* l = p -&gt; left;
        node* r = p -&gt; right;
        free(p);

        if ( r == NULL )
            return l;

        node* m = find_min(r);
        m -&gt; left = l;
        m -&gt; right = remove_min(r);        

        return balance(m);
    }

    return balance(p);
}

void free_tree(node* p)
{
    if ( !p )
        return;

    free_tree(p -&gt; left);
    free_tree(p -&gt; right);
    free(p);
}

int main(void)
{
    node* root = NULL;

    char c;
    int k, d;
    while ( scanf("%c", &amp;c) &amp;&amp; c != 'F' )
    {
        if ( c == 'A' )
        {
            scanf("%d %d", &amp;k, &amp;d);
            root = insert(root, k, d);
        }
        else if ( c == 'S' )
        {
            scanf("%d", &amp;k);
            node* n = search(root, k);
            if ( n ) 
                printf("%d %d\n", n -&gt; key, n -&gt; data);
        }
        else if ( c == 'D' )
        {
            scanf("%d", &amp;k);
            root = remove_item(root, k);
        }
    }

    free_tree(root);

    return 0;
}
Overall, this seems to be some well-crafted code that is clear, concise and doesn't leak memory.  Here are some things that may help you improve your code.

Use the appropriate #includes

In order to compile and link, this code requires the following two lines:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;


For the program to be complete, these should be listed, too.

Fix node deletion

There is a problem with the remove_item code.  In particular, if we construct a tree with just three items and then attempt to remove the root, the current code causes a crash because the left subtree is added before the call to remove_min(r). To fix that, simply swap the lines in remove_item so that this part of the code looks like this:

    node* m = find_min(r);
    m -&gt; right = remove_min(r);        
    m -&gt; left = l;


This is likely to be the problem that causes the time limit to be exceeded.