Binary Search Tree implementation
Firstly, in C, ALL_CAPS is generally used only for macros. Hence, I wouldn't use the name NODE as a typedef for your struct node, but instead something like typedef struct Node node_type;. Further, generally C is written using lowercase_with_underscores, so I'd rename it to struct node. 

Using an assert in your new_leaf function on what you get back from malloc is fine in my books, as this will terminate the process if the OS can't give you back any memory, in which case you're unlikely to be able to do anything anyway.

Your function int contains(NODE *node, int value) doesn't really need an assert. If the user gives you a NULL node, then you can immediately just return 0. Giving a NULL to this function shouldn't terminate the program. A similar argument can be made for max_height. 

Of course, the biggest problem is that no, your destroy function definitely does NOT clean up all the memory allocated by the program. Tools like valgrind can help to inform you if you have any memory leaks lurking around. In this case, however, it's very easy to see that the only memory that will be reclaimed is the memory for the root node (whatever you call destroy with).

Fixing this is pretty simple: it's just using a recursive algorithm that you've basically already used in insert and contains:

void destroy(node_type root)
{
    // If we have a non-NULL pointer, we need to
    // recursively free its left and right children,
    // and then free it.
    if(root) {
        destroy(root-&gt;left);
        destroy(root-&gt;right);
        free(root);
    }
}


A few other comments:


I'm not a big fan of 2 space indentation. It's not enough to (easily) visually scope blocks. I'd much rather 4 spaces.
You might want to start looking into how to user header files to split up interface and implementation as a next step (if you haven't already).
I'm not a big fan of explicitly having keeping track of what is a leaf with is_leaf. It means that any node that is down the bottom will have 2 extra dynamic allocations performed to have leaf values (see insert). Instead, I'd just set the left and right pointers to be NULL, and leave it at that. You can easily write an is_leaf function that simply checks that both pointers are NULL. 
The API is a bit deficient (no deletion of a value, for example), but I'm guessing this is done as a learning exercise, so that's ok.