Binary Search Tree implementation #include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;assert.h&gt;

typedef struct Node NODE;

struct Node {
  int value;
  int is_leaf;
  struct Node *right;
  struct Node *left;
};

NODE *new_leaf(void) {
  NODE *leaf = malloc(sizeof(NODE));
  assert(leaf);
  leaf-&gt;is_leaf = 1;
  leaf-&gt;value = 0;
  leaf-&gt;right = NULL;
  leaf-&gt;left = NULL;
  return leaf;
}

int insert(NODE *node, int value) {
  assert(node);
  if (node-&gt;is_leaf) {
    node-&gt;is_leaf = 0;
    node-&gt;value = value;
    node-&gt;left = new_leaf();
    node-&gt;right = new_leaf();
  } else if (node-&gt;value &lt; value) {
    return insert(node-&gt;left, value);
  } else if (node-&gt;value &gt; value) {
    return insert(node-&gt;right, value);
  }
  return -1;
}

int contains(NODE *node, int value) {
  assert(node);
  if (node-&gt;is_leaf) {
    return 0;
  } else if (node-&gt;value &lt; value) {
    return contains(node-&gt;left, value);
  } else if (node-&gt;value &gt; value) {
    return contains(node-&gt;right, value);
  } 
  return 1;
}

int max_height(NODE *node) {
  assert(node);
  if (node-&gt;is_leaf) {
    return 0;
  } 
  int left_height = max_height(node-&gt;left);
  int right_height = max_height(node-&gt;right);
  if (left_height &gt; right_height) {
    return 1 + left_height;
  } else {
    return 1 + right_height;
  }
}

void destroy(NODE *tree) {
  free(tree);
}


int main(void) {
  NODE *tree = new_leaf();
  insert(tree, 7);
  printf("contains 7? : %d\n", contains(tree, 7));
  insert(tree, 6);
  printf("contains 6? : %d\n", contains(tree, 6));
  insert(tree, 5);
  printf("contains 5? : %d\n", contains(tree, 5));
  printf("height should be 3, is : %d\n", max_height(tree));
  insert(tree, 8);
  printf("contains 8? : %d\n", contains(tree, 8));
  printf("height should be 3, is : %d\n", max_height(tree));
  printf("no contains 1? : %d\n", contains(tree, 9));
  destroy(tree);
}


Looking for general style advice, and if I missed any memory leaks. 

Specific question: does destroying the tree at the end free up all of the memory allocated for every node in the tree? If so, how? If not, how can I ensure that occurs? Also, am I using asserts correctly? It's very different than the languages I have used previously.
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.