Growing the tree without breaking the rule

Follow the same path search would take

To insert a value, walk the tree exactly like Lesson 4's search — compare, go left if smaller, go right if bigger. Search stops at NULL because the value is not there. Insertion does the same walk, and when it reaches that NULL, that is precisely where the new node belongs.

A duplicate value hits an equal comparison instead of NULL. A BST conventionally refuses duplicates rather than deciding arbitrarily where a second copy would go — the search function you wrote for Lesson 4 already returns that node, so insertion simply does nothing when it finds one.

struct Node *insert(struct Node *node, int value)
{
    if (node == NULL) {
        struct Node *fresh = malloc(sizeof(struct Node));
        fresh->data = value;
        fresh->left = fresh->right = NULL;
        return fresh;
    }

    if (value < node->data)
        node->left = insert(node->left, value);
    else if (value > node->data)
        node->right = insert(node->right, value);
    /* equal: already present, do nothing */

    return node;
}

Order decides shape

The same set of values produces a different-shaped tree depending on the order you insert them. Insert 30, 10, 50, 20, 40 and you get a short, wide tree. Insert 10, 20, 30, 40, 50 — already sorted — and every value becomes the right child of the last one, producing a tree that is really just a linked list wearing a tree's struct.

A degenerate tree loses everything Lesson 4 promised — height equals size, so search costs as much as Unit I's plain linear list did. Try both orders below and watch the shape.

What a BST is actually good for

A sorted array supports fast search too, but inserting into one means shifting every larger element over — the exact O(n) shifting cost you saw in CS105ES's array lessons. A BST gives you fast search and fast insertion at the same time, which is why it is the natural home for a sorted set that keeps growing: an autocomplete dictionary, a leaderboard of unique scores, or any collection where you need both 'is this here' and 'add this' to stay cheap.