How to Insert in BST in C: Simple Guide with Example

To insert in a BST in C, create a new node and recursively find the correct position by comparing values. Insert the new node where the left or right child is NULL, maintaining the BST property.

Syntax

The insertion function typically takes the root node and the value to insert. It returns the updated root after insertion.

• struct Node*: Pointer to a tree node.
• insert(struct Node* root, int value): Function to insert value into the BST rooted at root.
• Recursively moves left if value is less than current node's data, right if greater.
• Creates a new node when it finds a NULL position.

c

struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct 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 shows how to insert multiple values into a BST and print the tree in-order to verify the insertion order.

c

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

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

struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct 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 inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal of the BST: ");
    inorder(root);
    printf("\n");
    return 0;
}

Output

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

Common Pitfalls

Common mistakes when inserting in a BST include:

• Not handling the NULL root case, which causes crashes.
• Inserting duplicate values without a rule, which can break BST properties.
• Forgetting to update the parent's left or right pointer after recursive insertion.

Always return the updated root from the insert function to keep the tree connected.

c

/* Wrong: Not returning updated root */
struct Node* insert_wrong(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct Node));
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (value < root->data) {
        insert_wrong(root->left, value); // Missing assignment
    } else if (value > root->data) {
        insert_wrong(root->right, value); // Missing assignment
    }
    return root;
}

/* Right: Assign returned node */
struct Node* insert_right(struct Node* root, int value) {
    if (root == NULL) {
        struct Node* newNode = malloc(sizeof(struct 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

• Use recursion to find the correct spot for insertion.
• Return the new or unchanged root after insertion.
• Do not insert duplicates or decide a rule to handle them.
• Always check for NULL before accessing node pointers.

Key Takeaways

Always return the updated root pointer after insertion to maintain tree structure.

Insert recursively by comparing values and placing new nodes at NULL children.

Avoid inserting duplicate values or define a clear rule for duplicates.

Check for NULL nodes before accessing their members to prevent crashes.

Use in-order traversal to verify the BST property after insertion.