Binary Search Trees

1
2
3
4

typedef struct Node {
    int value;
    struct Node *left, *right;
} Node;

1
2
3
4
5
6
7
8
9
10

Node *insert(Node *root, int v) {
    if (!root) {
        Node *n = malloc(sizeof *n);
        n->value = v; n->left = n->right = NULL;
        return n;
    }
    if (v < root->value) root->left  = insert(root->left,  v);
    else if (v > root->value) root->right = insert(root->right, v);
    return root;
}

1
2
3
4
5
6
7
8
9
10
11
12

void inorder(const Node *n) {
    if (!n) return;
    inorder(n->left);
    printf("%d ", n->value);
    inorder(n->right);
}

void destroy(Node *n) {
    if (!n) return;
    destroy(n->left); destroy(n->right);
    free(n);            // children first, then self
}