C Academy · Lesson

Inserting into a BST

Build a binary search tree.

Inserting into a BST is a free C Academy lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

The BST Ordering Rule

A Binary Search Tree (BST) is a binary tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger.

This ordering is what lets us search, insert, and delete in time proportional to the tree's height.

Where a Value Belongs

To insert, we start at the root and compare. If the new value is smaller, we go left; if larger, we go right.

We repeat until we reach an empty spot (NULL), which is exactly where the new node belongs.

/* insert 7 into:
 *        10
 *       /  \
 *      5    15
 * 7 < 10 -> left;  7 > 5 -> right of 5
 */

The create_node Helper

Insertion builds new leaf nodes, so we reuse a constructor that allocates and initializes a node.

Both children start as NULL because a freshly inserted node is always a leaf.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->left = n->right = NULL;
    return n;
}

Recursive Insert

The cleanest insert is recursive and returns the (possibly new) subtree root.

If the subtree is empty, we return a fresh node. Otherwise we recurse left or right and reattach the result, then return the unchanged root.

Node *insert(Node *root, int value) {
    if (root == NULL)
        return create_node(value);
    if (value < root->value)
        root->left = insert(root->left, value);
    else if (value > root->value)
        root->right = insert(root->right, value);
    return root;  /* equal: ignore duplicate */
}

Why Return the Root

Returning the subtree root lets the parent reattach the link in one line: root->left = insert(root->left, v).

When the subtree was empty, the returned new node becomes the child. When it was not, the same root is returned and the link is unchanged.

/* The assignment does double duty:
 * - empty case: stores the new node
 * - non-empty:  stores the same pointer back (no-op)
 */
root->left = insert(root->left, value);

Handling Duplicates

Real BSTs must decide what to do with equal values. A common choice is to ignore duplicates, as our insert does by having no branch for the equal case.

Alternatives include keeping a count per node or always sending duplicates to one side.

if (value < root->value)
    root->left = insert(root->left, value);
else if (value > root->value)
    root->right = insert(root->right, value);
/* value == root->value -> do nothing */

Building a BST

Inserting a sequence of values produces a tree whose shape depends on the insertion order.

Here we insert several numbers and print the root's immediate children to confirm the ordering rule holds.

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

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

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

int main(void){
    Node *root = NULL;
    int data[] = {10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,data[i]);
    printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
    return 0;
}

An Iterative Insert

You can also insert without recursion. We walk down with a pointer, remembering the parent, until we find an empty slot.

Then we attach the new node to the correct side of that parent.

void insert_iter(Node **rootp, int value) {
    Node *cur = *rootp, *parent = NULL;
    while (cur) {
        parent = cur;
        cur = (value < cur->value) ? cur->left : cur->right;
    }
    Node *n = create_node(value);
    if (!parent) *rootp = n;
    else if (value < parent->value) parent->left = n;
    else parent->right = n;
}

Insertion Order Shapes the Tree

Inserting 1,2,3,4,5 in sorted order makes a degenerate tree that looks like a linked list, with height equal to the count.

Inserting in a balanced order keeps the height near log(n). Balance directly affects search speed.

/* sorted insert 1..5 ->
 * 1
 *  \
 *   2
 *    \
 *     3   (height = 4, like a list)
 */

Cost of Insertion

Each insertion walks one path from the root to a leaf, so it does work proportional to the tree's height.

For a balanced tree that is about log(n) comparisons; for a degenerate tree it can be n. This is why self-balancing trees exist.

Full Insert Demo

This program inserts values, then counts the nodes to confirm five distinct values were stored and a duplicate was ignored.

The duplicate 10 does not increase the count because insert drops equal values.

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

typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
    if(!r) return cn(v);
    if(v<r->value) r->left=insert(r->left,v);
    else if(v>r->value) r->right=insert(r->right,v);
    return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,10,20};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("count=%d\n", count(root));
    return 0;
}

Quick Check

Reason about insertion behaviour.

Recap

BST insertion compares the new value to each node, going left for smaller and right for larger, until an empty slot is found.

The recursive form returns the subtree root so the parent can reattach links cleanly. Insertion costs scale with tree height, so insertion order matters.

Frequently asked questions

Is the “Inserting into a BST” lesson free?

Yes — the full text of “Inserting into a BST” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.

What will I learn in “Inserting into a BST”?

Build a binary search tree. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start C Academy?

No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Inserting into a BST” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this C Academy lesson?

Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to C Academy