C Academy · Lesson

Searching and Freeing

Find nodes and release memory.

Searching and Freeing is a free C Academy lesson on CoddyKit — lesson 4 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.

Searching a BST

Searching exploits the ordering rule. At each node we compare the target with the node's value and move into just one subtree.

Because we discard half the remaining nodes at each step, search costs scale with the tree's height, not its size.

Recursive Search

The recursive search has two base cases: an empty subtree means not found, and a matching value means found.

Otherwise we recurse left or right depending on the comparison.

Node *search(Node *root, int target) {
    if (root == NULL || root->value == target)
        return root;
    if (target < root->value)
        return search(root->left, target);
    return search(root->right, target);
}

Iterative Search

Search can also be a simple loop, avoiding recursion overhead.

We follow pointers down the tree until we find the target or fall off the end at NULL.

Node *search_iter(Node *root, int target) {
    while (root != NULL) {
        if (target == root->value) return root;
        root = (target < root->value)
             ? root->left : root->right;
    }
    return NULL;  /* not found */
}

Search in Action

This program builds a BST and searches for a present and an absent value, printing whether each was found.

A non-NULL return means found; NULL means the value is not in the tree.

#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;
}
Node *search(Node *r,int t){
    if(!r||r->value==t) return r;
    return t<r->value ? search(r->left,t) : search(r->right,t);
}

int main(void){
    Node *root=NULL;
    int d[]={10,5,15,3,7};
    for(int i=0;i<5;i++) root=insert(root,d[i]);
    printf("7:%s 99:%s\n",
        search(root,7)?"found":"no",
        search(root,99)?"found":"no");
    return 0;
}

Finding the Minimum

In a BST the smallest value is the leftmost node: keep following left until it is NULL.

Symmetrically, the maximum is the rightmost node. These helpers matter for deletion and for range queries.

Node *find_min(Node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

Why Freeing Matters

Every node came from malloc, so every node must be returned with free. Forgetting to free leaks memory.

But you cannot free a node and then read its child pointers, so the order of freeing is critical.

Free in Post-Order

The safe way to free a tree is post-order: free both children first, then free the node itself.

This guarantees we read a node's left and right pointers before that node's memory is released.

void free_tree(Node *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

A Dangerous Wrong Order

If you free the node before recursing into its children, you create undefined behavior: you would dereference freed memory to reach the subtrees.

This is a classic use-after-free bug. Always free children first.

/* WRONG: use-after-free */
void bad_free(Node *root) {
    if (!root) return;
    free(root);                 /* freed here */
    bad_free(root->left);       /* reads freed memory! */
    bad_free(root->right);
}

Avoid Dangling Pointers

After free_tree returns, the original root pointer still holds the old address but the memory is gone.

Setting it back to NULL in the caller prevents accidental reuse of a dangling pointer.

free_tree(root);
root = NULL;   /* avoid a dangling pointer */

Counting Freed Nodes

We can confirm freeing works by counting nodes during the post-order walk, then freeing each one.

This program builds a tree, frees it, and reports how many nodes were released.

#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 free_count(Node *r){
    if(!r) return 0;
    int c = free_count(r->left) + free_count(r->right);
    free(r);
    return c + 1;
}

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

Search and Free Together

A complete lifecycle: build the tree, search it, then free it. Doing all three keeps programs correct and leak-free.

Tools like Valgrind can confirm that every malloc is matched by a free.

/* lifecycle
 * 1. insert values     (allocate)
 * 2. search as needed   (read-only)
 * 3. free_tree(root)    (deallocate)
 * 4. root = NULL        (avoid dangling)
 */

Quick Check

Reason about safe deallocation.

Recap

BST search compares and descends into one subtree per step, costing time proportional to height. The minimum is the leftmost node, the maximum the rightmost.

Free a tree in post-order so children are released before the parent, then set the root to NULL to avoid a dangling pointer.

Frequently asked questions

Is the “Searching and Freeing” lesson free?

Yes — the full text of “Searching and Freeing” 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 “Searching and Freeing”?

Find nodes and release memory. 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 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Searching and Freeing” 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