C binary search trees with malloc and free
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.
C
#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;
}