Lesson 11 · 11 of 20

A binary search tree · C

Build a binary search tree in C that counts words: recursive insertion, lookup, in-order traversal and freeing the tree.

C · A binary search tree in DMarlon Studio: the example's code and its output in the terminal

In a binary search tree each node has two children, left and right, and one rule: smaller words go to the left and bigger ones to the right. Thanks to that rule, a search walks down a single branch and, if the tree is balanced, rules out half of it at each level.

insert is recursive. When it reaches an empty spot (n == NULL), it creates the node with calloc, which leaves count at 0 and the children at NULL, and copies the word. Then it compares with strcmp: smaller goes into the left subtree, bigger into the right one, and equal adds one to count. A brand-new node therefore goes from 0 to 1, and a repeated word like fig reaches 3.

find does the same without recursion: until it finds the word, it moves down left or right. It returns the node or NULL, as with lime.

in_order visits the left subtree first, then the node, then the right subtree: an in-order traversal, which prints the words alphabetically without sorting anything. The root is melon because it was the first word inserted.

free_tree frees in post-order: both children first, then the node. The other way round, freeing the node would lose the pointers to its children.

Code · main.c

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct Node { char word[16]; int count; struct Node *left, *right; } Node;Node *insert(Node *n, const char *word) {  // smaller to the left, bigger to the right    if (n == NULL) {  // empty spot found: the new node goes here        if (!(n = calloc(1, sizeof *n))) exit(EXIT_FAILURE);  // count 0, children NULL        snprintf(n->word, sizeof n->word, "%s", word);    }    int cmp = strcmp(word, n->word);    if (cmp < 0) n->left = insert(n->left, word);    else if (cmp > 0) n->right = insert(n->right, word);    else n->count++;  // the word is here: new (0 -> 1) or repeated    return n;}const Node *find(const Node *n, const char *word) {  // one branch per level    while (n && strcmp(word, n->word) != 0) n = strcmp(word, n->word) < 0 ? n->left : n->right;    return n;}void in_order(const Node *n) {  // left, node, right: alphabetical order    if (n) { in_order(n->left); printf("  %-6s x%d\n", n->word, n->count); in_order(n->right); }}void free_tree(Node *n) { if (n) { free_tree(n->left); free_tree(n->right); free(n); } }int main(void) {    const char *words[] = {"melon", "fig", "pear", "apple", "kiwi", "fig", "plum", "apple", "fig"};    Node *root = NULL;  // an empty tree    for (int i = 0; i < 9; i++) root = insert(root, words[i]);    in_order(root);    printf("Root: %s, kiwi: %s, lime: %s\n", root->word,           find(root, "kiwi") ? "found" : "missing", find(root, "lime") ? "found" : "missing");    free_tree(root);  // children first, then the node itself    return 0;}

Output · cc main.c -o main && ./main

  apple  x2
  fig    x3
  kiwi   x1
  melon  x1
  pear   x1
  plum   x1
Root: melon, kiwi: found, lime: missing

Key points

Smaller to the left, bigger to the right.
Search and insert walk a single branch.
An in-order traversal gives the data sorted.
Free in post-order: children first, then the node.

Exercise

Write int height(const Node *n) (0 for NULL, otherwise 1 plus the taller child's height) and compare the tree's height with the one you get by inserting the words already sorted.