How to Create a Binary Search Tree in C: Syntax and Example

To create a binary search tree in C, define a struct for tree nodes with data and pointers to left and right children. Then write functions to insert nodes by comparing values and placing smaller values to the left and larger to the right.

Syntax

A binary search tree node in C is defined using a struct that contains an integer data and two pointers to its left and right child nodes. The insertion function compares the new value with the current node's data and recursively inserts it into the left subtree if smaller, or the right subtree if larger.

c

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

Example

This example creates a binary search tree by inserting several values, then prints the tree in-order to show the sorted order of elements.

c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {
    Node* root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(values) / sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }
    printf("Inorder traversal of the BST: ");
    inorderTraversal(root);
    printf("\n");
    return 0;
}

Output

Inorder traversal of the BST: 20 30 40 50 60 70 80 

Common Pitfalls

Common mistakes include not initializing new nodes properly, forgetting to handle the NULL root case, and inserting duplicate values without a clear rule. Also, not freeing memory can cause leaks.

Always check for NULL before accessing pointers and decide how to handle duplicates (ignore or count).

c

/* Wrong: Not checking for NULL before inserting */
Node* insert_wrong(Node* root, int value) {
    if (root == NULL) return NULL; /* Added to avoid dereferencing NULL */
    if (value < root->data) {
        root->left = insert_wrong(root->left, value); // root could be NULL here
    } else if (value > root->data) {
        root->right = insert_wrong(root->right, value);
    }
    return root;
}

/* Right: Check for NULL root before inserting */
Node* insert_right(Node* root, int value) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (value < root->data) {
        root->left = insert_right(root->left, value);
    } else if (value > root->data) {
        root->right = insert_right(root->right, value);
    }
    return root;
}

Quick Reference

• Node struct: Holds data and pointers to left/right children.
• Insert function: Recursively places new values in correct subtree.
• Traversal: Inorder traversal prints values sorted.
• Memory: Use malloc to create nodes and free memory when done.

Key Takeaways

Define a node struct with data and left/right pointers to build a binary search tree.

Insert nodes by comparing values and placing smaller ones left, larger ones right.

Always check for NULL before inserting to avoid crashes.

Use inorder traversal to print the tree in sorted order.

Manage memory carefully by allocating new nodes and freeing them when no longer needed.