No STL, No Shortcuts: Implementing DSA From Scratch in C

Every language gives you abstractions that make your life easier.

In C++, you reach for std::queue, std::vector, or std::map. You call push(), pop(), or insert(), and move on to solving the actual problem.

And that’s exactly what those abstractions are there for.

But recently, I wanted to step away from them.

Not because I don’t know how to use them, and not because using the standard library is somehow wrong. I wanted to challenge myself to understand the data structures at a lower level by building them myself.

So I decided to take a simple rule for my DSA practice:

No STL. No ready-made data structures. Build it myself.

And for this experiment, I chose C.

I already work with C and have been improving my understanding of it, but implementing DSA entirely from scratch felt like a good way to push that understanding further. Instead of treating a queue or a tree as something I could reach for, I wanted to think about how I would actually build one.

The first problem I picked was level-order traversal of a Binary Search Tree.

The traversal itself isn’t particularly complicated. What made it interesting was everything around it: creating the tree using structs and pointers, allocating nodes dynamically, implementing a queue from scratch, managing that queue while traversing the tree, and finally cleaning up the memory.

The algorithm was the easy part.

Building everything the algorithm depended on was the real challenge.

The tree

Start with the node. Nothing surprising here, but the self-referential struct is the first thing C makes you explicit about:

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

Note that the tag struct TreeNode has to appear before the typedef name exists — inside the body, TreeNode isn't a name yet, so the members have to be declared as struct TreeNode *. Small detail, but it's the kind of thing you never notice until the compiler makes you notice it.

Insertion is where things got interesting:

void insertTreeNode(TreeNode **head, int data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    TreeNode *curr = *head;
    if (curr) {
        while (curr) {
            if (curr->data < data) {
                if (curr->right == NULL) {
                    curr->right = node;
                    break;
                }
                curr = curr->right;
            } else {
                if (curr->left == NULL) {
                    curr->left = node;
                    break;
                }
                curr = curr->left;
            }
        }
    } else {
        *head = node;
    }
}

The signature isTreeNode **head, not TreeNode *head, and that double pointer is the whole reason this function works.

C passes everything by value. If I took a TreeNode *head and assigned head = node inside the function, I'd be reassigning a local copy of the pointer. The caller's variable would still be, NULL and the tree would never get a root. Taking the address of the caller's pointer — TreeNode ** — lets me write through it and actually change what the caller is holding.

This is the same idea as a C++ reference-to-pointer, except C makes you spell it out. Every insert after the first one modifies curr->left or curr->right, which is a field of a struct on the heap, so those don't need the extra indirection. Only the very first insert does. One special case, one extra star.

I also made a decision here that’s worth stating out loud rather than leaving implicit: equal values go left. curr->data < data Sends you right; everything else goes left. That's a policy choice, not a law of BSTs, and different implementations pick differently.

The queue

Level-order traversal needs a FIFO queue. Two obvious options in C: a linked list, or a fixed array.

I went with the array:

#define QUEUE_SIZE 100
typedef struct Queue {
    TreeNode *data[QUEUE_SIZE];
    int front;
    int back;
} Queue;

The reasoning: a linked-list queue means one malloc per enqueue, and I'm already allocating for every tree node. Doubling the allocation count for a structure that's purely scratch space felt wasteful. The array lives on the stack, costs nothing to set up, and every slot is contiguous — which the cache appreciates.

The tradeoff is that it’s fixed size, and I’ll come back to that in a minute because it turned out to matter more than I expected.

The operations are small enough to read in one pass:

void init(Queue *queue) {
    queue->front = -1;
    queue->back = -1;
}
void insert(Queue *queue, TreeNode *node) {
    queue->data[queue->back + 1] = node;
    if (queue->front == -1) {
        queue->front++;
    }
    queue->back++;
}
TreeNode *pop(Queue *queue) {
    TreeNode *node = queue->data[queue->front];
    queue->front++;
    return node;
}
int size(Queue *queue) {
    return queue->back - queue->front + 1;
}

The -1 sentinel marks an empty queue. front advances on every pop, back advances on every insert, and size is just the distance between them. When they cross, the queue is empty.

Get Devanshu Pathak’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Also worth noticing: the queue storesTreeNode *, not TreeNode. It holds pointers into the tree, not copies of nodes. Copying would mean the traversal walks a snapshot instead of the real structure, and free would get complicated fast.

Putting them together

void levelOrderTraversal(TreeNode *head) {
    Queue queue;
    init(&queue);
    insert(&queue, head);
    printf("%d\n", head->data);
while (size(&queue)) {
        int n = size(&queue);
        while (n) {
            TreeNode *node = pop(&queue);
            if (node->left) {
                printf("%d ", node->left->data);
                insert(&queue, node->left);
            }
            if (node->right) {
                printf("%d ", node->right->data);
                insert(&queue, node->right);
            }
            n--;
        }
        printf("\n");
    }
}

The trick that separates levels is capturing size(&queue) into n before the inner loop starts. Everything currently in the queue belongs to the same level. Process exactly that many nodes, and whatever got enqueued during the pass is the next level, waiting cleanly. Print a newline, repeat.

Without that snapshot you’d get a flat list of values with no level structure, which is a different (and less useful) traversal.

For this tree:

insertTreeNode(&head, 15);
insertTreeNode(&head, 7);
insertTreeNode(&head, 18);
insertTreeNode(&head, 12);
insertTreeNode(&head, 45);
insertTreeNode(&head, 3);
insertTreeNode(&head, 16);

the output is:

15
7 18
3 12 16 45

Which is the tree, level by level.

Then cleanup, which no language with a garbage collector would have made me write:

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

Post-order, and it has to be post-order. Free the root first, and you’ve thrown away the pointers to both subtrees — every remaining node is leaked and unreachable in the same instruction. Children first, parent last.

What Could Be Improved

The implementation works for the tree I tested, but it isn’t a perfect or production-ready queue. The queue uses a fixed-size array and never reuses the slots after elements are removed, so a sufficiently large tree could eventually write past the allocated array. There are also a few edge cases worth handling, such as checking whether malloc() fails and making sure levelOrderTraversal() handles an empty tree. For this exercise, I kept the implementation intentionally simple; the goal was to understand how the pieces work rather than build a fully robust queue implementation.

Splitting it into files

Once the thing worked, it was one 120-line main.c doing three unrelated jobs. Splitting it up is what turns a snippet into something you'd extend later:

tree.h    tree.c      — TreeNode, insert, freeTree
queue.h   queue.c     — Queue and its operations
main.c                — traversal + driver

The headers declare the types and function prototypes; the .c files hold the implementations. Every header gets an include guard:

#ifndef QUEUE_H
#define QUEUE_H

#include "tree.h"

#define QUEUE_SIZE 100

typedef struct Queue {
    TreeNode *data[QUEUE_SIZE];
    int front;
    int count;
} Queue;

void init(Queue *queue);
int  insert(Queue *queue, TreeNode *node);
TreeNode *pop(Queue *queue);
int  size(Queue *queue);
#endif

Without the guard, including queue.h twice in the same translation unit redefines struct Queue and the compiler rejects it. queue.h needs tree.h because it mentions TreeNode, and the guards make that nesting safe.

Then compile:

gcc -Wall -Wextra -o traversal main.c tree.c queue.c

-Wall -Wextra is not optional if you're doing this to learn. Half the mistakes above are things a compiler will tell you about for free, and running without warnings on is choosing not to be told.

What I Actually Got Out of It

It wasn’t speed. The STL version would be faster to write and probably just as efficient in practice.

What I gained was understanding.

TreeNode **head stopped being syntax I recognised and became something I understood. A queue stopped being a push() and pop() abstraction—I had to think about how it actually works.

I also learned that “it works” doesn’t always mean “it’s correct.” Testing the code made me think about the cases I hadn’t considered.

You can read about pointers, queues, memory, and trees.

But building them yourself makes you understand them differently.

And that’s exactly what I wanted from this exercise.

You can find the complete implementation here: level_order_traversal.c