Binary search trees
A binary search tree keeps the keys in order: everything to the left of a node is smaller, everything to the right is larger. A search follows one path from the root, so a balanced tree of n keys takes about log n steps, the cost of binary search from lesson 49 with insertion included. The two extra pointers per node are the price of that order, and the shape of the tree decides how much of the logarithmic cost survives.
Insert and traverse
A node holds a value and two child pointers. Insert compares the value with the node and recurses into the matching side, creating a leaf when it reaches a null pointer. The in-order traversal prints left subtree, node, right subtree, which yields the keys in ascending order.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
static struct Node *insert(struct Node *root, int value)
{
if (root == NULL) {
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
return NULL;
}
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
if (value < root->value) {
root->left = insert(root->left, value);
} else if (value > root->value) {
root->right = insert(root->right, value);
}
return root;
}
static void print(const struct Node *node)
{
if (node == NULL) {
return;
}
print(node->left);
printf("%d ", node->value);
print(node->right);
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
struct Node *root = NULL;
int values[7] = {5, 3, 8, 1, 4, 7, 9};
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
print(root);
printf("\n");
free_tree(root);
return 0;
}
gcc -Wall -Wextra insert.c -o insert
./insert
1 3 4 5 7 8 9
The values were inserted in an order that keeps the tree balanced, so the shape has three levels. Inserting 1, 2, 3, 4, 5 in that order would build a chain with five levels, the worst case of a tree, and the search would degrade to the linear scan from lesson 49.
Search
A search is a while loop that compares and moves to one child, so it does not need recursion. The example builds the same tree from automatic nodes, which keeps the code short, and asks for a value that exists and one that does not. Returning an int instead of a pointer keeps the ownership simple.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
static int contains(const struct Node *root, int value)
{
while (root != NULL) {
if (value == root->value) {
return 1;
}
root = value < root->value ? root->left : root->right;
}
return 0;
}
int main(void)
{
struct Node n1 = {1, NULL, NULL};
struct Node n4 = {4, NULL, NULL};
struct Node n3 = {3, &n1, &n4};
struct Node n7 = {7, NULL, NULL};
struct Node n9 = {9, NULL, NULL};
struct Node n8 = {8, &n7, &n9};
struct Node n5 = {5, &n3, &n8};
printf("4: %d\n", contains(&n5, 4));
printf("6: %d\n", contains(&n5, 6));
return 0;
}
gcc -Wall -Wextra search.c -o search
./search
4: 1
6: 0
The search for 6 reaches the leaf 4 and takes its right child, which is null, so the value is absent. The number of steps is the depth of the value's path plus one, and the depth is what a balanced tree keeps small.
Deletion
Deleting a leaf or a node with one child replaces it with that child. Deleting a node with two children is the interesting case: its in-order successor is the smallest value of the right subtree, that value is copied into the node, and the successor is deleted from the right subtree. The tree keeps its order and loses one node.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
static struct Node *insert(struct Node *root, int value)
{
if (root == NULL) {
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
return NULL;
}
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
if (value < root->value) {
root->left = insert(root->left, value);
} else if (value > root->value) {
root->right = insert(root->right, value);
}
return root;
}
static struct Node *minimum(struct Node *node)
{
while (node->left != NULL) {
node = node->left;
}
return node;
}
static struct Node *remove_value(struct Node *root, int value)
{
if (root == NULL) {
return NULL;
}
if (value < root->value) {
root->left = remove_value(root->left, value);
} else if (value > root->value) {
root->right = remove_value(root->right, value);
} else {
if (root->left == NULL) {
struct Node *right = root->right;
free(root);
return right;
}
if (root->right == NULL) {
struct Node *left = root->left;
free(root);
return left;
}
struct Node *next = minimum(root->right);
root->value = next->value;
root->right = remove_value(root->right, next->value);
}
return root;
}
static void print(const struct Node *node)
{
if (node == NULL) {
return;
}
print(node->left);
printf("%d ", node->value);
print(node->right);
}
int main(void)
{
struct Node *root = NULL;
int values[7] = {5, 3, 8, 1, 4, 7, 9};
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
root = remove_value(root, 5);
print(root);
printf("\n");
while (root != NULL) {
root = remove_value(root, root->value);
}
return 0;
}
gcc -Wall -Wextra delete.c -o delete
./delete
1 3 4 7 8 9
The root 5 was replaced by its successor 7, and the right subtree lost that node. The final loop deletes every remaining value, which frees each node through the same path; a real program would call free_tree instead, because deleting one by one costs a search per node.
Freeing the parent first
A tree is freed from the leaves up, because the children are reachable only through the parent. Freeing the node first and then reading node->left uses memory that no longer belongs to the program. GCC warns about both reads, and AddressSanitizer reports the first one:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free(node);
free_tree(node->left);
free_tree(node->right);
}
int main(void)
{
struct Node *root = malloc(sizeof *root);
struct Node *child = malloc(sizeof *child);
if (root == NULL || child == NULL) {
return 1;
}
root->value = 2;
root->left = child;
root->right = NULL;
child->value = 1;
child->left = NULL;
child->right = NULL;
free_tree(root);
return 0;
}
gcc -fsanitize=address -g -Wall -Wextra uaf.c -o uaf
./uaf 2>&1 | head -n 8
uaf.c: In function 'free_tree':
uaf.c:17:5: warning: pointer 'node' used after 'free' [-Wuse-after-free]
17 | free_tree(node->right);
| ^~~~~~~~~~~~~~~~~~~~~~
uaf.c:15:5: note: call to 'free' here
15 | free(node);
| ^~~~~~~~~~~
uaf.c:16:5: warning: pointer 'node' used after 'free' [-Wuse-after-free]
16 | free_tree(node->left);
| ^~~~~~~~~~~~~~~~~~~~~
uaf.c:15:5: note: call to 'free' here
15 | free(node);
| ^~~~~~~~~~~
=================================================================
==952==ERROR: AddressSanitizer: heap-use-after-free on address 0x75c665c20018 at pc 0x593711d73229 bp 0x7ffe06114410 sp 0x7ffe06114400
The report is cut after its first line; it continues with the stack of the read. The fix is the order in the first section: recurse into left and right while the node is still alive, and free it last.
Exercises
- Write a function that returns the height of the tree, and print it for the balanced example and for keys inserted in ascending order.
- Add a function that finds the largest value without a full traversal.
- Change the node to hold a string key and an int value, and compare the keys with strcmp.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What order does an in-order traversal of a search tree produce?
Answer
Ascending key order from left to right
The traversal visits the left subtree, then the node, then the right subtree, which is ascending for a search tree.
-
How does a search move through a binary search tree?
Answer
It follows one child per comparison
Each comparison rules out one subtree, so the path follows the left or right child until the key or a null pointer is found.
-
Which node replaces a deleted node that has two children?
Answer
The smallest value of its right subtree
The in-order successor is the smallest value on the right, and copying it into the node keeps the order.
-
What happens to the shape when keys are inserted in ascending order?
Answer
The tree becomes a chain of one child per node
Every new key is larger than the previous one, so it becomes the right child and the search degrades to a linear walk.
-
What does this program print?
#include <stdio.h> #include <stdlib.h> struct N{int v;struct N*l,*r;}; static struct N*ins(struct N*x,int v){if(!x){x=malloc(sizeof*x);x->v=v;x->l=x->r=NULL;return x;}if(v<x->v)x->l=ins(x->l,v);else if(v>x->v)x->r=ins(x->r,v);return x;} static void pr(const struct N*x){if(!x)return;pr(x->l);printf("%d ",x->v);pr(x->r);} int main(void){struct N*r=NULL;int a[7]={5,3,8,1,4,7,9};for(int i=0;i<7;i++)r=ins(r,a[i]);pr(r);printf("\n");return 0;}Answer
1 3 4 5 7 8 9
The in-order traversal of the seven inserted keys prints them from smallest to largest.
-
What does this program print?
#include <stdio.h> struct N{int v;struct N*l,*r;}; static int has(const struct N*x,int v){while(x){if(v==x->v)return 1;x=v<x->v?x->l:x->r;}return 0;} int main(void){struct N n1={1,0,0},n4={4,0,0},n3={3,&n1,&n4},n7={7,0,0},n9={9,0,0},n8={8,&n7,&n9},n5={5,&n3,&n8};printf("%d %d\n",has(&n5,4),has(&n5,6));return 0;}Answer
1 0
Four is present and returns 1, while the search for six reaches a null child and returns 0.
-
What does this program print after removing 5?
#include <stdio.h> #include <stdlib.h> struct N{int v;struct N*l,*r;}; static struct N*ins(struct N*x,int v){if(!x){x=malloc(sizeof*x);x->v=v;x->l=x->r=NULL;return x;}if(v<x->v)x->l=ins(x->l,v);else if(v>x->v)x->r=ins(x->r,v);return x;} static struct N*min(struct N*x){while(x->l)x=x->l;return x;} static struct N*del(struct N*x,int v){if(!x)return 0;if(v<x->v)x->l=del(x->l,v);else if(v>x->v)x->r=del(x->r,v);else{if(!x->l){struct N*r=x->r;free(x);return r;}if(!x->r){struct N*l=x->l;free(x);return l;}struct N*n=min(x->r);x->v=n->v;x->r=del(x->r,n->v);}return x;} static void pr(const struct N*x){if(!x)return;pr(x->l);printf("%d ",x->v);pr(x->r);} int main(void){struct N*r=NULL;int a[7]={5,3,8,1,4,7,9};for(int i=0;i<7;i++)r=ins(r,a[i]);r=del(r,5);pr(r);printf("\n");return 0;}Answer
1 3 4 7 8 9
The successor 7 replaces 5, and the remaining keys print in ascending order.
-
What does GCC warn about in
free_treewhen the node is freed first?Answer
That the children are read after the free
The recursive calls read
node->leftandnode->rightfrom a block that was already released. -
How should a tree be freed?
Answer
Free the children first, then the parent
The child pointers live in the parent, so both subtrees are released before the node that holds them.
-
What happens if a node with two children is replaced by its left child only?
Answer
The right subtree is lost and the order breaks
The left child does not contain the right subtree, so the replacement drops nodes and breaks the search order.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 with the AddressSanitizer runtime on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev