A binary search tree in C

Insert descends left or right; search follows the same path.

#include <stdlib.h>

typedef struct Tree {
    int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

Tree *insert(Tree *root, int key) {
    if (root == NULL) {
        Tree *node = malloc(sizeof *node);
        if (node != NULL) {
            node->key = key;
            node->left = NULL;
            node->right = NULL;
        }
        return node;
    }
    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }
    return root;
}

int contains(const Tree *root, int key) {
    while (root != NULL) {
        if (key == root->key) {
            return 1;
        }
        root = (key < root->key) ? root->left : root->right;
    }
    return 0;
}

How it works

1. Every left subtree holds smaller keys, every right one larger.
2. Recursion mirrors the structure exactly.
3. An in-order walk visits the keys in sorted order.

Keywords and builtins used here

• NULL
• Tree
• const
• contains
• else
• if
• insert
• int
• return
• sizeof
• struct
• typedef
• while

The run, in numbers

Lines

35

Characters to type

600

Tokens

206

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 118 seconds.

Type this snippet

Step 1 of 4 in Trees, tables & heaps, step 11 of 20 in Data structures & algorithms.

← Previous Next →