How do I actually insert a node without breaking the BST rules?

The golden rule of a Binary Search Tree is simple: everything smaller than the current node goes to the left, and everything larger goes to the right. If you follow that consistently, your tree stays sorted. The trick is to treat the insertion as a search. You're essentially searching for the one spot where the value should have been, and when you hit a NULL pointer, that's where you plant the new node.

I prefer using a recursive approach here because it maps perfectly to the tree structure. Here is how I usually write it:

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

Node* insert(Node* root, int value) {
    // If we've reached a leaf position, create the node
    if (root == NULL) {
        Node* newNode = malloc(sizeof(Node));
        newNode->data = value;
        newNode->left = newNode->right = NULL;
        return newNode;
    }

    // Otherwise, keep diving down the tree
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }

    return root;
}

Notice that I'm returning the root pointer. This is a clean way to handle the case where the tree is initially empty, as it allows the caller to capture the very first node created as the new root of the whole tree.

Which traversal method actually gives me the data in sorted order?

You'll hear about three main types: Pre-order, In-order, and Post-order. If your goal is to print the contents of the BST in ascending order, you want In-order traversal. The name is a bit of a misnomer—it doesn't mean "the first thing you do," but rather that you visit the root node in between the left and right children.

Think of it as: "Go as far left as possible, print the value, then try to go right."

void printInOrder(Node* root) {
    if (root == NULL) return;

    printInOrder(root->left);       // Visit left subtree
    printf("%d ", root->data);      // Visit current node
    printInOrder(root->right);      // Visit right subtree
}

If you swapped these lines around, you'd get entirely different results. Pre-order (Root, Left, Right) is great for cloning a tree, and Post-order (Left, Right, Root) is what you'd use if you were writing a function to delete the entire tree from the bottom up to avoid memory leaks.

Why is my program crashing when I try to insert into an empty tree?

This is the most common "gotcha" I see. It usually happens because of how C handles pointers. If you pass your root pointer (which is NULL) into a function and try to update it inside that function, you're only updating a local copy of that pointer. The original root in your main() remains NULL.

You have two ways to fix this. The first is what I did in the code above: return the updated pointer and assign it back in main like this: root = insert(root, 10);.

The second way is to use a pointer-to-a-pointer (a double pointer). It looks scarier, but it's very efficient because you're modifying the actual address of the root. I'll leave that for the more advanced lessons, but for now, just remember that in C, if you want a function to change where a pointer points, you either need to return the new address or pass the address of the pointer itself.

📋 Practical Task

Build a Sorted Employee ID Registry

You need to create a simple system to manage employee IDs. Write a C program that does the following:

• Defines a Node structure for a Binary Search Tree.
• Implements an insert function that maintains the BST property.
• Implements an inOrderTraversal function to print the IDs.
• In your main function, insert the following IDs in this exact order: 50, 30, 70, 20, 40, 60, 80.
• Print the final tree using the in-order traversal. If your implementation is correct, the output should be the IDs in perfectly ascending order (20 30 40 50 60 70 80).