C Binary Tree: Create, Insert, Traverse

Each node has left and right children. Insert recursively: smaller goes left, bigger goes right. In-order traversal visits in sorted order.

A binary tree is a hierarchical data structure — each node has at most two children. Today's tree is a binary search tree (BST): for every node, left children are smaller, right children are larger. That gives O(log n) lookups (when balanced).

The basic shape

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

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

Node *create_node(int value) {
  Node *n = malloc(sizeof(Node));
  n->data = value;
  n->left = NULL;
  n->right = NULL;
  return n;
}

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;
}

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

int count(Node *root) {
  if (root == NULL) return 0;
  return 1 + count(root->left) + count(root->right);
}

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

int main() {
  Node *root = NULL;
  root = insert(root, 50);
  insert(root, 30);
  insert(root, 70);
  insert(root, 20);
  insert(root, 40);
  insert(root, 60);

  inorder(root);   // 20 30 40 50 60 70
  printf("\n");
  free_tree(root);
}

The Node struct

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

Two child pointers — left and right. Both NULL for a leaf node.

The structure is naturally recursive: each child is itself a node with its own children.

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;
}

Three cases:

1. Empty tree. Create a new node; that's the new root.
2. Value smaller. Insert into left subtree.
3. Value larger or equal. Insert into right subtree.

The function takes a root and returns a (possibly new) root. Each level updates its child pointer with the result.

For the first insert, root is NULL → returns a new node → that's our tree's new root. Subsequent inserts walk down the tree without modifying the root.

After the BST insert: 50 at the root; 30 and 70 as children; 20, 40, 60 as grandchildren.

        50
       /  \
      30   70
     / \   /
    20 40 60

In-order traversal

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

Recursively: left subtree, current, right subtree.

For a BST, this visits values in sorted ascending order — magic side effect of the smaller-left/bigger-right invariant.

For the example tree: 20 30 40 50 60 70.

Counting nodes

int count(Node *root) {
  if (root == NULL) return 0;
  return 1 + count(root->left) + count(root->right);
}

Recurse: 1 (current) + count of left subtree + count of right subtree. Empty subtree contributes 0.

Free the whole tree

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

Post-order — free children before the parent. If you free the parent first, you've lost the pointers to children; they leak.

This is one of the fundamental traversal orders. Episode 51 covers all three — in-order, pre-order, post-order — in detail.

Tree height

int height(Node *root) {
  if (root == NULL) return 0;
  int lh = height(root->left);
  int rh = height(root->right);
  return 1 + (lh > rh ? lh : rh);
}

The number of edges from root to deepest leaf. Empty tree has height 0; single node, height 1.

For balanced BSTs, height ≈ log₂(n). For pathological cases (inserts in sorted order), the tree degenerates to a linked list with height = n.

Why BST: O(log n) lookups

A balanced BST has O(log n) height. Lookup walks from root, going left or right based on comparison. Each step halves the remaining search space:

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

For 1,000,000 nodes, ~20 comparisons. Linear search would average 500,000.

Caveat: balance must be maintained. Inserting 1, 2, 3, ..., 1000 into a basic BST gives a degenerate one-line tree — O(n) lookups. Real BSTs (red-black, AVL) self-balance.

Iteration vs recursion

Recursion is natural for trees but uses stack frames per level. For pathological 10,000-node trees (each on the right): 10,000 stack frames → potential stack overflow.

Iterative traversal uses an explicit stack:

void inorder_iter(Node *root) {
  Node *stack[100];   // explicit stack
  int top = -1;
  Node *current = root;

  while (current != NULL || top >= 0) {
    while (current != NULL) {
      stack[++top] = current;
      current = current->left;
    }
    current = stack[top--];
    printf("%d ", current->data);
    current = current->right;
  }
}

Same traversal, no recursion. Useful for huge trees or when stack is precious.

When to use a tree

• Sorted data with frequent inserts. Sorted arrays are O(n) to insert; BSTs are O(log n).
• Range queries. "Find all values between A and B" — BST in-order.
• Hierarchical data. Filesystems, parsed expressions, scene graphs.

For straight key-value lookup, a hash table is faster (O(1) avg vs O(log n)). Trees win when you need order.

Common mistakes

Forgetting to handle NULL. Recursive functions must base-case on NULL or they crash on empty subtrees.

Insert returning value not assigned. insert(root, 5) should be root = insert(root, 5) for the first insert (when root was NULL).

Free in wrong order. Freeing the parent first loses pointers to children.

Inserting equal values. Should they go left, right, or be deduplicated? Pick a policy.

Treating a degenerate BST as O(log n). Inserting sorted data builds a linear chain. Real applications use self-balancing trees (AVL, red-black).

Confusing data == with data != NULL. The first compares the integer; the second... doesn't make sense (data is an int). For Node * checks, use root != NULL.

What's next

Episode 51: traversal — in-order, pre-order, post-order. The three depth-first traversal orders, with use cases for each.

Recap

Binary tree: each node has left and right. BST invariant: smaller in left subtree, bigger in right. Insert, search, traversal are recursive. In-order traversal of a BST gives sorted output. Free in post-order. Balanced BST: O(log n) operations. Pathological insert order can degenerate to O(n) — real applications use self-balancing trees. Use hash tables for unordered lookup; BSTs when order matters.

Next episode: traversal orders.