Binary search trees

typedef struct TreeNode {
    int key;
    struct TreeNode *left, *right;
} TreeNode;

            50
          /    \
        30      70
       /  \       \
     20    40      80

every key in 50's left subtree (20, 30, 40) < 50 < every key in its right subtree (70, 80)

TreeNode *insert(TreeNode *root, int key) {
    if (root == NULL) {
        TreeNode *n = malloc(sizeof *n);
        if (!n) return NULL;                    /* real code should report this */
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    /* equal keys: ignored in this simple version */
    return root;
}

int contains(const TreeNode *root, int key) {
    while (root) {
        if (key == root->key) return 1;
        root = (key < root->key) ? root->left : root->right;   /* go one way only */
    }
    return 0;
}

void in_order(const TreeNode *t) {
    if (!t) return;
    in_order(t->left);              /* smaller keys first */
    printf("%d ", t->key);
    in_order(t->right);             /* then larger keys */
}
/* for the tree above: 20 30 40 50 70 80 */

void free_tree(TreeNode *t) {
    if (!t) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);                        /* post-order: the node last */
}

int height(const TreeNode *t) {
    if (!t) return 0;
    int l = height(t->left), r = height(t->right);
    return 1 + (l > r ? l : r);
}

inserting 10, 20, 30, 40, 50 in sorted order:
10
  \
   20
     \
      30          ← a "tree" that is really a linked list: height 5, search O(n)
        \
         40
           \
            50