Binary Search Tree in C: Bugs, Deletion, Sorted Input

Revised November 2026. This tutorial first appeared in Korean in 2021. Rebuilt with Apple clang 21, the C example did not compile as C (2 errors); compiled as C++ it produced 2 warnings, and when run it reported that it had found a key that was not in the tree. AddressSanitizer caught a heap-use-after-free the moment the root was deleted. The causes were a missing return in the search function and a main() that threw away the delete function's return value. The core logic, deleting a node with two children, was correct. Below are the fixed code, its real output, and a measurement of what sorted input does to a plain BST.

This article is for anyone implementing a binary search tree by hand, especially if deletion is where you got stuck. The short version: a BST answers search, insert and delete in time proportional to its height, using one rule: smaller keys go left, larger keys go right. The trouble is that the height depends on insertion order. It can be about log n or it can be n. Inserting 50,000 keys in sorted order made lookups roughly 900 times slower in our test, which is why production code uses a balanced tree such as std::map or C#'s SortedDictionary instead.

The BST rule and how search works

A BST is a binary tree with one ordering rule added: for every node, all keys in its left subtree are smaller and all keys in its right subtree are larger. It is binary search laid out as a tree instead of a sorted array, and in exchange you can insert and delete in the middle without shifting elements.

In this tree (keys inserted in the order 10, 5, 1, 6, 17, 14, 21), searching for 14 goes right at 10, left at 17, and hits 14. Searching for 16 follows the same path to 14, tries to go right, finds NULL, and reports "not found". The number of comparisons is at most the height plus one.

The 2021 search function forgot to return its recursive calls:

    else if (Tree->Data > findData)
        searchNode(Tree->Left, findData);   // result discarded
    else
        searchNode(Tree->Right, findData);  // result discarded
}                                           // falls off the end with no value

clang warned about it:

warning: non-void function does not return a value in all control paths [-Wreturn-type]

and the warning turned into wrong behavior. In an -O0 build, searching for 16, which is not in the tree, printed "found", and then the delete function said "not found". The caller had read whatever happened to be left in the return register and treated it as a non-NULL pointer:

해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0xf5578058 입니다.
해당하는 노드를 찾을 수 없습니다.
현재 트리 출력: 1 5 6 10 14 17 21

(The program's messages are Korean: "Found the node! Removing it. The node is at 0xf5578058", then "Could not find the node", then "Current tree: …".) The same source compiled as C at -O2 happened to print "not found" correctly, which is typical of undefined behavior: the result changes with the optimization level. Compiled as C++ with UBSan, it stopped at the first search:

algorithm-binary-search-tree-0.c:19:7: runtime error: execution reached the end of a value-returning function without returning a value

The fixed search is a loop, so it uses no stack however deep the tree gets:

Node* search(Node* t, int key) {
    while (t && t->data != key)
        t = key < t->data ? t->left : t->right;
    return t;
}

Every error and warning in the 2021 code

Here is everything the current compiler reported (Apple clang 21, -Wall -Wextra):

1. Does not compile as C. In typedef struct Node { Node* Left; ... } Node; the name Node is not yet a typedef inside the struct body. C++ accepts it, which suggests the 2021 code was built with a C++ compiler.

algorithm-binary-search-tree-0.c:5:5: error: must use 'struct' tag to refer to type 'Node'
    5 |     Node* Left;
      |     ^
      |     struct

2. -Wreturn-type: the missing return shown above.
3. -Wformat: node addresses were printed with %#x. A pointer is 8 bytes on a 64-bit system, so printing it as unsigned int gives a wrong value; in our runs every node printed as the same 0xf5578058. Pointers need %p. The new version simply does not print addresses.

warning: format specifies type 'unsigned int' but the argument has type 'Node *' (aka 'struct Node *') [-Wformat]

4. An input loop that never ends. while(1) { scanf(...); } keeps going after end of input, reusing the last value forever. After four inputs our run kept re-processing 17. The loop is now while (scanf("%d", &key) == 1).

Insert, delete, and the use-after-free

Insert follows the search path and attaches the new node at the empty spot. The 2021 insertNode crashed on an empty tree (it dereferenced a NULL root), and when the key already existed it neither linked nor freed the new node. leaks --atExit reported that node as a ROOT LEAK in a small test. The new insert returns the root, so an empty tree works, and it allocates nothing for a duplicate.

Delete has three cases:

• No children: free the node and give the parent NULL.
• One child: free the node and give the parent that child, which moves up one level.
• Two children: find the smallest key in the right subtree (the in-order successor), copy it into the node, then delete the successor from the right subtree. The successor never has a left child, so that delete is one of the easy cases.

The 2021 removeNode implemented this correctly. We ran 5,000 rounds of 100 random inserts and deletes over 64 keys (500,000 operations), checking the BST ordering and the element count after every step, and it passed every time as long as the caller stored the returned root. The 2021 main did not: it called removeNode(Tree, input); and ignored the result. If the root has only one child left and you delete it, the function frees the root and returns the child as the new root, but main's Tree still points at freed memory. Deleting 1, 5, 6 and then 10 was enough for ASan:

==63477==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000001c30 at pc 0x00010051a828 bp 0x00016f8e62e0 sp 0x00016f8e62d8
READ of size 8 at 0x603000001c30 thread T0
    #0 0x00010051a824 in printTree bst-min.c:79
    #1 0x00010051ac38 in main bst-min.c:105

freed by thread T0 here:
    #0 0x000100ea5368 in free+0x7c (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x41368)
    #1 0x00010051a72c in removeNode bst-min.c:70
    #2 0x00010051ac24 in main bst-min.c:103

Without ASan, the freed memory often still holds its old contents, so the program can print a plausible tree, which makes this bug more dangerous rather than less. The fixed program:

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

typedef struct Node {
    struct Node* left;          /* 2021: Node* left;  -> error in C */
    struct Node* right;
    int data;
} Node;

static Node* create_node(int data) {
    Node* n = malloc(sizeof *n);
    if (!n) { perror("malloc"); exit(1); }
    n->left = n->right = NULL;
    n->data = data;
    return n;
}

Node* search(Node* t, int key) {
    while (t && t->data != key)                     /* 2021: recursive call without return */
        t = key < t->data ? t->left : t->right;
    return t;
}

Node* insert(Node* t, int data) {                   /* returns the (possibly new) root */
    if (t == NULL) return create_node(data);
    if (data < t->data)      t->left  = insert(t->left, data);
    else if (data > t->data) t->right = insert(t->right, data);
    /* equal: already present, nothing allocated */
    return t;
}

static Node* find_min(Node* t) {
    while (t && t->left) t = t->left;
    return t;
}

Node* remove_node(Node* t, int data) {              /* returns the new root of this subtree */
    if (t == NULL) return NULL;                     /* not found */
    if (data < t->data)      t->left  = remove_node(t->left, data);
    else if (data > t->data) t->right = remove_node(t->right, data);
    else if (t->left && t->right) {                 /* two children */
        Node* succ = find_min(t->right);            /* in-order successor */
        t->data = succ->data;
        t->right = remove_node(t->right, succ->data);
    } else {                                        /* zero or one child */
        Node* child = t->left ? t->left : t->right;
        free(t);
        return child;
    }
    return t;
}

void print_inorder(const Node* t) {
    if (!t) return;
    print_inorder(t->left);
    printf("%d ", t->data);
    print_inorder(t->right);
}

void free_tree(Node* t) {
    if (!t) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

int main(void) {
    Node* root = NULL;
    int init[] = {10, 5, 1, 6, 17, 14, 21};
    for (size_t i = 0; i < sizeof init / sizeof init[0]; ++i) root = insert(root, init[i]);

    int key;
    while (scanf("%d", &key) == 1) {                /* 2021: while(1) -> endless loop at EOF */
        if (search(root, key)) {
            root = remove_node(root, key);          /* 2021: return value ignored */
            printf("removed %d: ", key);
        } else {
            printf("%d not found: ", key);
        }
        print_inorder(root);
        printf("\n");
    }
    free_tree(root);
    return 0;
}

It compiles with zero warnings under -Wall -Wextra and runs clean under ASan and UBSan. Real output for the input 10 6 5 14 17 16 10 1 21, which starts by deleting the two-child root:

removed 10: 1 5 6 14 17 21
removed 6: 1 5 14 17 21
removed 5: 1 14 17 21
removed 14: 1 17 21
removed 17: 1 21
16 not found: 1 21
10 not found: 1 21
removed 1: 21
removed 21:

In the first line the root 10 is deleted and 14, the smallest key in its right subtree, takes its place. At the end the tree is empty and the program exits normally. ASan on macOS has no leak checker (detect_leaks is not supported on this platform), so we ran leaks --atExit: 0 leaks for 0 total leaked bytes.

Sorted input: when the tree becomes a list (measured)

Every BST operation costs O(height). Random insertion order gives an expected height of O(log n). Sorted insertion order attaches every new key to the right end, producing a degenerate tree that is really a linked list. We inserted the keys 0 to 49,999 in two orders and then looked up all 50,000 keys in random order (Apple clang 21 -O2, Apple M1 Pro, second of two runs; iterative insert).

Same data, different order, about 900 times slower lookups. A height of 38 is about 2.4 times log2(50,000) ≈ 15.6, which is normal for a randomly built BST. In the sorted tree, each lookup chases 25,000 pointers on average.

Real data is sorted more often than you would expect: auto-increment IDs, timestamps, a CSV exported in key order. And height n is not only a speed problem. The recursive insert and free_tree above use one stack frame per level, so on a degenerate tree they crash with a stack overflow somewhere in the hundreds of thousands of levels, as measured in our tree traversal article. That is why the benchmark used an iterative insert.

What to use instead: balanced search trees

A balanced BST rotates nodes during insert and delete so that the height stays O(log n). You rarely need to write one yourself:

• C++: std::map and std::set. To meet the standard's O(log n) guarantees, both libc++ and libstdc++ implement them as red-black trees. In the table above, std::set took 6.05 ms for the lookups even with sorted input.
• C#: SortedDictionary<TKey, TValue> and SortedSet<T>. Inspecting .NET 10 with reflection, SortedDictionary's private _set field is a TreeSet that derives from SortedSet, and its nodes carry a NodeColor property with the values Black and Red. It is a red-black tree. Inserting the 50,000 sorted keys took 43.51 ms and 50,000 ContainsKey calls took 16.09 ms (Release, after a warm-up round).

How to choose:

A hand-written BST is a great learning exercise and a common interview question. In production code, where you cannot control the insertion order, it is safer to leave it out.

Summary

• BST rule: left < node < right. Search, insert and delete are all O(height).
• To delete a node with two children, copy the minimum of its right subtree and delete that node instead. The 2021 code did this correctly and passed 500,000 randomized checks.
• Real bugs in the 2021 code: a C compile error, a missing return in search (it "found" absent keys), a pointer printed with %#x, a main() that ignored the new root (heap-use-after-free), and an endless loop at end of input. All fixed.
• A BST built from 50,000 sorted keys had height 50,000 and lookups about 900 times slower. In real code, use a red-black tree: std::map or SortedDictionary.