C in 100 Seconds: Binary Tree

Binary Tree — Create, Insert, Traverse

A binary tree has nodes with left and right children. When smaller values go left and larger go right, it becomes a binary search tree — lookups, inserts, and traversals are all efficient.

The Node Struct

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

Two child pointers instead of one next pointer. Each node can branch in two directions.

Recursive Insert

Node *insert(Node *root, int value) {
  if (root == NULL) return create_node(value);
  if (value < root->data)
    root->left = insert(root->left, value);
  else
    root->right = insert(root->right, value);
  return root;
}

If the current node is NULL, create a new node. Otherwise, compare and recurse left or right. Each call moves one level deeper until it finds an empty spot.

Inorder Traversal

void inorder(Node *root) {
  if (root == NULL) return;
  inorder(root->left);
  printf("%d ", root->data);
  inorder(root->right);
}

Go left, print current, go right. This visits every node in sorted order — that is the defining property of a BST.

Count and Free

count returns 1 + left count + right count. free_tree frees children before the parent — otherwise we lose access to them.

Student Code

Try it yourself: episode50/bintree.c