When you first encounter the need to store a collection of data that stays sorted, your instinct is probably to reach for an array. It's simple, it's contiguous, and if you keep it sorted, you can use binary search to find things incredibly quickly. I've seen plenty of developers stick with this approach far longer than they should, simply because it feels "safe." But as soon as you need to actually modify that data—adding a new entry or deleting an old one—the array becomes a liability.

The cost of shifting memory

Imagine we're building a system to track employee IDs in a corporate directory. If you use a sorted array, inserting a new ID isn't just a matter of putting it at the end. You have to find the correct spot to maintain the order, and then you have to shift every single subsequent element one slot to the right to make room. If your directory has 10,000 employees and you insert a new hire with a low ID number, you're potentially moving 9,999 integers in memory. That's an $O(n)$ operation that gets progressively more painful as your dataset grows. It's a classic case of paying a huge tax on every write just to keep the reads fast.

Trading contiguous memory for pointers

This is where the Binary Tree—specifically the Binary Search Tree (BST)—comes in. Instead of forcing everything into a single block of memory, we create small, independent nodes that point to each other. In C, this means moving from a simple array to a struct that contains the data and two pointers: one for the left child (smaller values) and one for the right child (larger values).

typedef struct Node {
    int employeeID;
    struct Node* left;
    struct Node* right;
} Node;

The beauty of this approach is that we no longer shift memory. When you want to insert a new ID, you just "walk" down the tree—left if the new ID is smaller, right if it's larger—until you hit a NULL pointer. At that point, you malloc a new node and hang it off the leaf. You've just turned a potentially massive memory shift into a few pointer hops. I personally find the recursive nature of this much more elegant; you're essentially solving the same problem on a smaller version of the tree until you find the empty spot.

Where the pointer approach can break

Now, I have to give you a warning. Binary trees aren't a magic bullet. The efficiency of a BST depends entirely on its "balance." If you insert your employee IDs in perfectly sorted order (e.g., 101, 102, 103, 104), your tree doesn't actually look like a tree—it looks like a linked list. Every node just has a right child.

In that specific scenario, your search time collapses from $O(\log n)$ back to $O(n)$. You've kept the overhead of pointers without getting any of the speed benefits of the tree structure. This is why, in a production environment, you'd eventually move toward "Self-Balancing" trees like AVL or Red-Black trees, but for now, understanding the fundamental shift from contiguous arrays to linked nodes is the hurdle you need to clear.

📋 Practical Task

Implementing a Corporate ID Insertion Engine

Your task is to implement the insertion logic for the Binary Search Tree discussed in this lesson. You need to write a function that takes the root of a tree and an integer ID, and returns the updated root after the ID has been inserted in the correct position.

Requirements:

• Define the Node struct as shown in the lesson.
• Write a function Node* insert(Node* root, int id).
• The function must handle the case where the tree is initially empty (root is NULL).
• Use malloc to allocate memory for new nodes.
• Ensure that IDs smaller than the current node go to the left and larger IDs go to the right.

Test Case: Insert the following IDs in this exact order: 50, 30, 70, 20, 40, 60, 80. Then, write a simple helper function to print the tree "In-Order" (Left, Root, Right). If your implementation is correct, the output should be the sorted list: 20, 30, 40, 50, 60, 70, 80.