C binary search trees with malloc and free

Before you start

C structs, pointers, recursion, and malloc.

Allocate tree nodes dynamically, traverse them in order, and release every node.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A tree node in C is a struct with a value and two pointers to child nodes, where NULL means no child. Nodes are allocated with malloc, so the program owns the memory and must release it with free. A recursive insert function walks down one path and attaches the new node at the first NULL pointer it reaches.

An in-order traversal visits the left subtree, the node, and then the right subtree, which gives the values of a binary search tree in sorted order. Freeing a tree must be done in post-order: free the children first, and then the node itself, or the pointers to the children are lost. A tool such as Valgrind or AddressSanitizer reports leaks and invalid frees.

Code example

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

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

static Node *insert(Node *root, int value) {
  if (root == NULL) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) {
      exit(1);
    }
    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 in_order(const Node *root) {
  if (root == NULL) {
    return;
  }
  in_order(root->left);
  printf(" %d", root->value);
  in_order(root->right);
}

static int height(const Node *root) {
  if (root == NULL) {
    return 0;
  }
  int l = height(root->left);
  int r = height(root->right);
  return 1 + (l > r ? l : r);
}

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

int main(void) {
  Node *root = NULL;
  int values[] = {50, 30, 70, 20, 40, 60, 80, 40};
  for (int i = 0; i < 8; i++) {
    root = insert(root, values[i]);
  }
  printf("in order:");
  in_order(root);
  printf("\n");
  printf("height: %d\n", height(root));
  free_tree(root);
  return 0;
}

Output

in order: 20 30 40 50 60 70 80
height: 3

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <stdio.h>

2#include <stdlib.h>

4typedef struct Node {

5 int value;

6 struct Node *left;

7 struct Node *right;

8} Node;

10static Node *insert(Node *root, int value) {

11 if (root == NULL) {

12 Node *node = malloc(sizeof *node);

13 if (node == NULL) {

14 exit(1);

15 }

16 node->value = value;

17 node->left = NULL;

18 node->right = NULL;

19 return node;

20 }

21 if (value < root->value) {

22 root->left = insert(root->left, value);

23 } else if (value > root->value) {

24 root->right = insert(root->right, value);

25 }

26 return root;

27}

29static void in_order(const Node *root) {

30 if (root == NULL) {

31 return;

32 }

33 in_order(root->left);

34 printf(" %d", root->value);

35 in_order(root->right);

36}

38static int height(const Node *root) {

39 if (root == NULL) {

40 return 0;

41 }

42 int l = height(root->left);

43 int r = height(root->right);

44 return 1 + (l > r ? l : r);

45}

47static void free_tree(Node *root) {

48 if (root == NULL) {

49 return;

50 }

51 free_tree(root->left);

52 free_tree(root->right);

53 free(root);

54}

56int main(void) {

57 Node *root = NULL;

58 int values[] = {50, 30, 70, 20, 40, 60, 80, 40};

59 for (int i = 0; i < 8; i++) {

60 root = insert(root, values[i]);

61 }

62 printf("in order:");

63 in_order(root);

64 printf("\n");

65 printf("height: %d\n", height(root));

66 free_tree(root);

67 return 0;

68}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A new node is allocated on the heap when an empty spot is reached.	`—`	—
Smaller values go left. Equal values, like the second 40, are ignored.	`—`	—
Visit the whole left subtree first, so smaller values are printed before the node.	`—`	—
Seven values in a balanced shape make a tree of height 3.	`—`	in order: 20 30 40 50 60 70 80 height: 3
Free the children before the node itself.	`—`	in order: 20 30 40 50 60 70 80 height: 3

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

Cost and common mistakes

Insert and search O(h) for height h, which is O(log n) if balanced and O(n) in the worst case.

Forgetting free_tree leaks every node. Freeing the root first would lose the pointers to the children.
Inserting sorted values makes a chain, and the recursion depth equals n. Self-balancing trees avoid that.
malloc may return NULL. The example stops the program in that case.

Try it yourself

Which function visits nodes in the order 50 30 20 40 70 60 80?

Reveal answer and reasoning

A pre-order traversal: print the node first, then the left subtree, then the right subtree.