C binary search trees with malloc and free

Allocate tree nodes dynamically, traverse them in order, and release every node.

#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

Explanation

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.

Explore the dry run

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

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.

C binary search trees with malloc and free

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading